ECS 120 Lecture Notes - Lecture 3: Bradbury Thompson, Empty String, General Idea
Week 1
Lecture 1
Syllabus, Textbook, TA’s, grading
1. Finite State Machines abbreviated as FSM
a. What is a finite state machine
i. A FSM way is a method of checking if a machine can recognize a
certain language. The machine has two options, it will either accept
or reject its input.
b. How do you know which state to start from?
i. Look at the state that has an arrow coming into it from “nowhere”
ii. For the example below it is S1.
iii. The start state is known as the initial state
c. How do you know if the language is accepted?
i. Look for the state with two circles around it.
ii. In our example below it is S4.
d. Explanation of Diagram:
i. Diagram has 4 states : S1, S2, S3, S4
ii. Not every input is accepted.
iii. Not every state can see every letter.
iv. (see next lecture for more information about this)
e. Name some strings that are accepted by this?
i. aac, ac, aaaaacbd, aacdaaac
f. S2 can stay in S2 forever.
Mainpoint of lecture:
find more resources at oneclass.com
find more resources at oneclass.com
Exposre to what a FSM looks like. Functionality and details are left unclear, and are
explaiend in later lectures.
This was just a breif exposure to what a FSM is.
Lecture 2 DFSM
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
Syllabus, textbook, ta"s, grading: finite state machines abbreviated as fsm, what is a finite state machine, a fsm way is a method of checking if a machine can recognize a certain language. Look at the state that has an arrow coming into it from nowhere . Look for the state with two circles around it. Functionality and details are left unclear, and are explaiend in later lectures. This was just a breif exposure to what a fsm is. List of strings accepted: 101, 01, 000001 1001001. 0&1s: looks at lots of diagrams and this concept becomes easy to understand, s is the initial state. Look at which state their is an arrow coming on from no where : accept states, there can be multiple, These are the states with double circles around them. If we are in state 1, and we see input of 1 (see below for how input is read) we.