4 Questions
What are the three conditions for a finite automaton M to accept a string w?
- The machine starts in the start state.
- It goes from state to state according to the transition function.
- It accepts its input if it ends up in an accept state.
In the context of finite automata, what is the purpose of assigning states to possibilities?
To track the information about the input string as it is being read
In the construction of finite automaton E1 to recognize strings with an odd number of 1s, the automaton assigns states corresponding to whether the number of 1s seen so far is ___ or ___.
even, odd
How does finite automaton E2 recognize the regular language of strings containing the substring '001'?
E2 skips over 1s, notes a 0 followed by a 1, keeps track of symbols in the pattern '001', and transitions between states based on inputs.
Study Notes
Formal Definition of Computation
- A finite automaton M = (Q, Σ, δ, q0, F) accepts a string w = w1w2…wn if a sequence of states r0, r1, …, rn in Q exists with three conditions:
- r0 = q0
- δ(ri, wi+1) = ri+1, for i = 0, …, n-1
- rn ∈ F
- M recognizes language A if A = {w | M accepts w}
Designing Finite Automata
- To design a finite automaton, determine the necessary information to remember about the input string as it is being read
- Represent this information as a finite list of possibilities
- Assign a state to each possibility
- Determine the transitions by seeing how to go from one possibility to another upon reading a symbol
- Set the start state to the state corresponding to the possibility associated with having seen 0 symbols so far
- Set the accept states to those corresponding to possibilities where you want to accept the input string
Example: Finite Automaton E1
- Designed to recognize the language of all strings with an odd number of 1s
- The possibilities are:
- even so far
- odd so far
- States are assigned to each possibility
- Transitions are set to flip state on a 1 and stay put on a 0
- Start state is qeven
- Accept state is qodd
Example: Finite Automaton E2
- Designed to recognize the regular language of all strings that contain the string 001 as a substring
- The possibilities are:
- haven't just seen any symbols of the pattern
- have just seen a 0
- have just seen 00
- have seen the entire pattern 001
- States are assigned to each possibility
- Transitions are set based on the possibilities and the input symbols
- Start state is q
- Accept state is q001
Regular Operations
- Three operations on languages are defined:
- Union (A ∪ B)
- Concatenation (A ∘ B)
- Star operation (A*)
- The star operation is a unary operation that applies to a single language
- It works by attaching any number of strings in A together to get a string in the new language
- The empty string "" is always a member of A*, no matter what A is
Learn about the formal definition of computation in finite automata, building on state diagrams and 5-tuples. Understand how finite automata compute and formalize the process mathematically.
Make Your Own Quizzes and Flashcards
Convert your notes into interactive study material.
Get started for free
