Ch.2: Nondeterminism
Week 2 of the book "Automata, Formal Languages, and Turing Machines" by Emre Sermutlu (2020) 2.1. The Idea of NFA 2.2. The Formal Definition of NFA 2.3. Epsilon Transitions 2.4. NFA - DFA equivalence
49 flashcards · Computer Science · by lakesare
Part of Textbooks › Automata, Formal Languages, and Turing Machines (Emre Sermutlu) · 14 courses
[The Idea of NFA] NFA is short for Nondeterministic Finite Automaton.
[The Idea of NFA] In which three ways can an NFA differ from a DFA?
More than one transition For a given symbol, a state may have more than one transition. Example: two arrows labelled 111 leave the same state. No transition For a given symbol, a state may have no transition. Example: a state with an arrow for 111 but none for 000 . Epsilon labels Arrows may be labelled ε\varepsilonε (epsilon). Example: an arrow labelled ε\varepsilonε is followed without reading an input symbol. An NFA showing all three: the first state has two arrows for 111 , the third state…
[The Idea of NFA] Nondeterminism is a kind of parallel computation.
An NFA follows all possible transitions at the same time, as several copies of the machine.
[The Idea of NFA] An NFA is in state qqq and reads a symbol for which several arrows leave qqq . What happens?
The machine branches: one copy of the machine continues along each arrow. All the resulting machines are followed for the rest of the input.Example: q1q_1q1 has arrows labelled 111 to q1q_1q1 and to q2q_2q2 . On input 111 the machine splits into one copy in q1q_1q1 and one in q2q_2q2 .
[The Idea of NFA] An NFA is in state qqq and reads a symbol for which no arrow leaves qqq . What happens?
That machine dies: it is not followed any further. Equivalently, it moves into a trap state labelled ∅\varnothing∅ and stays there.
[The Idea of NFA] When does an NFA accept an input string?
When at least one of its parallel machines is in an accept state after the whole input is read. Machines that died or ended in non-accept states do not matter.
[The Idea of NFA] Over Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} , which strings does this NFA accept?
The strings whose second symbol from the end is 111 . A DFA for the same language is much more complicated.Example: 011001100110 is accepted, 010101010101 is not.
[The Idea of NFA] NFA over {0,1}\{0, 1\}{0,1} : q1q_1q1 loops on 0,10, 10,1 ; q1→1q2q_1 \overset{1}{\to} q_2q1→1q2 ; q2→0,1q3q_2 \overset{0, 1}{\to} q_3q2→0,1q3 ; q3q_3q3 is the only accept state and has no outgoing arrows.This NFA accepts exactly the strings whose second symbol from the end is 111 . Why?
At every 111 , one copy moves to q2q_2q2 ; that copy is in q3q_3q3 at the end exactly when the 111 was second from the end. A copy in q3q_3q3 that reads any further symbol dies, so only a 111 read exactly two steps before the end leads to acceptance.
[The Idea of NFA] NFA over {0,1}\{0, 1\}{0,1} : q1q_1q1 loops on 0,10, 10,1 ; q1→1q2q_1 \overset{1}{\to} q_2q1→1q2 ; q2→0,1q3q_2 \overset{0, 1}{\to} q_3q2→0,1q3 ; q3q_3q3 is the only accept state and has no outgoing arrows.Which states are the parallel machines in after each symbol of the input 110110110 ? Is 110110110 accepted?
{q1}→1{q1,q2}→1{q1,q2,q3}→0{q1,q3}\{q_1\} \overset{1}{\to} \{q_1, q_2\} \overset{1}{\to} \{q_1, q_2, q_3\} \overset{0}{\to} \{q_1, q_3\}{q1}→1{q1,q2}→1{q1,q2,q3}→0{q1,q3} : accepted. On the last 000 , the copy in q3q_3q3 dies and the copy in q2q_2q2 moves to q3q_3q3 .
[The Formal Definition of NFA] A nondeterministic finite automaton is a 5-tuple (Q,Σ,δ,q0,F)(Q, \Sigma, \delta, q_0, F)(Q,Σ,δ,q0,F) . What is each component?
QQQ a finite set of states Σ\SigmaΣ a finite alphabet δ\deltaδ the transition function δ:Q×Σε→2Q\delta : Q \times \Sigma_\varepsilon \to 2^Qδ:Q×Σε→2Q Example: δ(q2,b)={q1,q3}\delta(q_2, b) = \{q_1, q_3\}δ(q2,b)={q1,q3} q0q_0q0 the start state, q0∈Qq_0 \in Qq0∈Q FFF the set of accept states, F⊆QF \subseteq QF⊆Q
[The Formal Definition of NFA] In the definition of an NFA, what do Σε\Sigma_\varepsilonΣε and 2Q2^Q2Q denote?
Σε=\Sigma_\varepsilon = Σε= Σ∪{ε}\Sigma \cup \{\varepsilon\}Σ∪{ε} ; 2Q=\ 2^Q = 2Q= the set of all subsets of QQQ . Example: for Q={q1,q2}Q = \{q_1, q_2\}Q={q1,q2} , 2Q={∅,{q1},{q2},{q1,q2}}2^Q = \{\varnothing, \{q_1\}, \{q_2\}, \{q_1, q_2\}\}2Q={∅,{q1},{q2},{q1,q2}} .
[The Formal Definition of NFA] How does the formal definition of an NFA differ from that of a DFA?
Only in the transition function: an NFA has δ:Q×Σε→2Q\delta : Q \times \Sigma_\varepsilon \to 2^Qδ:Q×Σε→2Q , a DFA has δ:Q×Σ→Q\delta : Q \times \Sigma \to Qδ:Q×Σ→Q . An NFA's δ\deltaδ also takes ε\varepsilonε as input, and gives a set of states as output. The empty set is a possible output.
[The Formal Definition of NFA] Give the transition function δ\deltaδ of this NFA.
δ(q1,a)={q2}, δ(q2,b)={q1,q3}, δ(q3,b)={q1}\boldsymbol{\delta(q_1, a) = \{q_2\}, \ \delta(q_2, b) = \{q_1, q_3\}, \ \delta(q_3, b) = \{q_1\}}δ(q1,a)={q2}, δ(q2,b)={q1,q3}, δ(q3,b)={q1} , all other values ∅\varnothing∅ . In particular δ(q1,b)=δ(q2,a)=δ(q3,a)=∅\delta(q_1, b) = \delta(q_2, a) = \delta(q_3, a) = \varnothingδ(q1,b)=δ(q2,a)=δ(q3,a)=∅ , and every ε\varepsilonε -transition is ∅\varnothing∅ .
[The Formal Definition of NFA] NFA over {a,b}\{a, b\}{a,b} with start state q1q_1q1 and accept state q3q_3q3 : δ(q1,a)={q2}\delta(q_1, a) = \{q_2\}δ(q1,a)={q2} , δ(q2,b)={q1,q3}\delta(q_2, b) = \{q_1, q_3\}δ(q2,b)={q1,q3} , δ(q3,b)={q1}\delta(q_3, b) = \{q_1\}δ(q3,b)={q1} , all other values ∅\varnothing∅ .Which strings does this NFA accept?
Strings made of blocks ababab and abbabbabb that end with the block ababab . q1→aq2→bq1q_1 \overset{a}{\to} q_2 \overset{b}{\to} q_1q1→aq2→bq1 and q1→aq2→bq3→bq1q_1 \overset{a}{\to} q_2 \overset{b}{\to} q_3 \overset{b}{\to} q_1q1→aq2→bq3→bq1 return to q1q_1q1 ; acceptance needs a final q1→aq2→bq3q_1 \overset{a}{\to} q_2 \overset{b}{\to} q_3q1→aq2→bq3 .Example: ababab , abababababab , abbababbababbab are accepted; abbabbabb and aabaabaab are not.
[The Formal Definition of NFA] Give the state diagram of an NFA over {0,1}\{0, 1\}{0,1} that recognizes the strings that start with 111111111 .
Three 111 -arrows in a row into an accept state that loops on 0,10, 10,1 . If a 000 occurs among the first three symbols, the machine dies.
[The Formal Definition of NFA] Give the state diagram of an NFA over {a,b}\{a, b\}{a,b} that recognizes the strings that start with ababab or start with aaabaaabaaab .
Branch on the first aaa : one path reads bbb , the other reads aabaabaab ; both end in one accept state that loops on a,ba, ba,b . The union of two languages is easy to build as an NFA.
[Epsilon Transitions] What does an ε\varepsilonε -transition do?
It moves the machine to another state without reading anything from the input. When an NFA is in a state with an ε\varepsilonε -arrow, it branches: one copy stays, one copy follows the arrow.Example: with q1→εq2q_1 \overset{\varepsilon}{\to} q_2q1→εq2 , an NFA in q1q_1q1 is also in q2q_2q2 before reading the next symbol.
[Epsilon Transitions] Which strings does this NFA accept?
aaa and abaabaaba , and nothing else. Without the ε\varepsilonε -arrow the NFA accepts only abaabaaba . The ε\varepsilonε -arrow skips the part that reads ababab .
[Epsilon Transitions] Which language does this NFA recognize?
{abna∣n≥1}\boldsymbol{\{ab^na \mid n \ge 1\}}{abna∣n≥1} The ε\varepsilonε -arrow back to the second state lets the NFA read bbb again.Example: abaabaaba , abbaabbaabba , abbbaabbbaabbba are accepted; aaaaaa is not.
[Epsilon Transitions] Which language does this NFA recognize?
{abna∣n≥1}∪{bna∣n≥0}\boldsymbol{\{ab^na \mid n \ge 1\} \cup \{b^na \mid n \ge 0\}}{abna∣n≥1}∪{bna∣n≥0} The lower ε\varepsilonε -arrow lets the NFA start in the third state without reading aaa . From there it can read aaa at once, or go back along the upper ε\varepsilonε -arrow and read bbb 's.Example: aaa , bababa , bbabbabba , abaabaaba are accepted; ababab is not.
[Epsilon Transitions] You have NFAs for languages AAA and BBB . How do you build an NFA for A∪BA \cup BA∪B ?
Add a new start state with ε\varepsilonε -transitions to the start states of both NFAs. The two machines then run in parallel, and the new NFA accepts when either of them accepts. Example: AAA = strings containing 111111 (top), BBB = strings not containing 000000000 (bottom), over {0,1}\{0, 1\}{0,1} .
[Epsilon Transitions] NFA over {0,1}\{0, 1\}{0,1} for the strings not containing 000000000 : states B1,B2,B3B_1, B_2, B_3B1,B2,B3 , all accepting, start B1B_1B1 ; B1→1B1B_1 \overset{1}{\to} B_1B1→1B1 , B1→0B2B_1 \overset{0}{\to} B_2B1→0B2 , B2→1B1B_2 \overset{1}{\to} B_1B2→1B1 , B2→0B3B_2 \overset{0}{\to} B_3B2→0B3 , B3→1B1B_3 \overset{1}{\to} B_1B3→1B1 .What does each state record, and what happens on a third 000 in a row?
B1,B2,B3B_1, B_2, B_3B1,B2,B3 : the input read so far ends in 000 , 111 , 222 zeros. A third 000 has no arrow, so that machine dies. Every string without 000000000 keeps a machine alive, so all three states accept.Example: 100110011001 goes B1→B1→B2→B3→B1B_1 \to B_1 \to B_2 \to B_3 \to B_1B1→B1→B2→B3→B1 : accepted.
[Epsilon Transitions] Over {0,1}\{0, 1\}{0,1} : find an NFA for the strings with at least one 111 , where the number of 000 's after the last 111 is 3n3n3n with n≥1n \ge 1n≥1 . What is the key idea?
After each 111 , branch: one copy assumes this 111 is the last and counts the 000 's in groups of three, the other copy continues. The copy that counts can read only 000 's, so it reaches acceptance only if its 111 was the last one.Example: 100010001000 and 010000000100000001000000 are accepted; 101010 , 111 and 100011000110001 are not.
[Epsilon Transitions] Describe the language this NFA recognizes.
ak b2m cn+1\boldsymbol{a^k \, b^{2m} \, c^{n+1}}akb2mcn+1 , k,m,n≥0\ k, m, n \ge 0 k,m,n≥0 Any number of aaa 's (possibly zero), then an even number of bbb 's (possibly zero), then one or more ccc 's.Example: ccc , abbcabbcabbc , aaccaaccaacc are accepted; abcabcabc is not.
[Epsilon Transitions] Describe the language this NFA recognizes.
an\boldsymbol{a^n}an or bn\boldsymbol{b^n}bn or a(ba)n\boldsymbol{a(ba)^n}a(ba)n , n≥0\ n \ge 0 n≥0 Each ε\varepsilonε -arrow starts one of three machines; the NFA accepts if one of them accepts.Example: ε\varepsilonε , aaaaaaaaa , bbbbbb , ababaababaababa are accepted; ababab is not.
[NFA - DFA equivalence] When are two machines equivalent?
When they recognize the same language.
[NFA - DFA equivalence] Theorem Every NFA has … ?
an equivalent DFA. So NFAs are not more powerful than DFAs, although the DFA usually has more states.Proof idea: build a DFA whose states are the sets of NFA states.
[NFA - DFA equivalence] To convert an NFA with nnn states into a DFA, how many states does the DFA get, and what are they?
2n\boldsymbol{2^n}2n states, one for each subset of the NFA's states. The state for the subset {q1,q2}\{q_1, q_2\}{q1,q2} is written q12q_{12}q12 .Example: an NFA with states {q1,q2}\{q_1, q_2\}{q1,q2} gives DFA states ∅,q1,q2,q12\varnothing, q_1, q_2, q_{12}∅,q1,q2,q12 .
[NFA - DFA equivalence] What is the ε\varepsilonε -closure of a state qqq of an NFA?
The set of all states that can be reached from qqq through ε\varepsilonε -transitions (including qqq itself). Example: with ε\varepsilonε -arrows q1→q4q_1 \to q_4q1→q4 and q1→q7q_1 \to q_7q1→q7 , or with q1→q4q_1 \to q_4q1→q4 and q4→q7q_4 \to q_7q4→q7 , the ε\varepsilonε -closure of q1q_1q1 is q147={q1,q4,q7}q_{147} = \{q_1, q_4, q_7\}q147={q1,q4,q7} .
[NFA - DFA equivalence] When converting an NFA into a DFA, what are the steps for the DFA's start state, transitions and accept states?
Start state the ε\varepsilonε -closure of the NFA's start state Example: NFA start q1q_1q1 with q1→εq2q_1 \overset{\varepsilon}{\to} q_2q1→εq2 gives DFA start q12q_{12}q12 . Transitions from a set of states on symbol xxx : the set of all states the NFA reaches from them on xxx , together with their ε\varepsilonε -closures Example: NFA arrows q1→aq2q_1 \overset{a}{\to} q_2q1→aq2 , q1→aq4q_1 \overset{a}{\to} q_4q1→aq4 , q1→aq5q_1 \overset{a}{\to} q_5q1→aq5 give the DFA transition q1→aq2…
[NFA - DFA equivalence] Why does the DFA built from an NFA with nnn states usually need far fewer than 2n2^n2n states?
Not all subsets occur in a computation: only the sets reachable from the start state are needed. Example: an NFA with 4 states has 24=162^4 = 1624=16 subsets, but its equivalent DFA may use only 5 of them.
[NFA - DFA equivalence] Find a DFA that recognizes the same language as this NFA.
States q1,q24,q234,q34,∅q_1, q_{24}, q_{234}, q_{34}, \varnothingq1,q24,q234,q34,∅ ; accepting q24,q234,q34q_{24}, q_{234}, q_{34}q24,q234,q34 . q24q_{24}q24 stands for the set {q2,q4}\{q_2, q_4\}{q2,q4} . Only 5 of the 24=162^4 = 1624=16 subsets occur.The language: aaa , and all strings that start with aaaaaa .
[NFA - DFA equivalence] Find a DFA equivalent to this NFA over Σ={a,b}\Sigma = \{a, b\}Σ={a,b} .
q1→aq23q_1 \overset{a}{\to} q_{23}q1→aq23 , q1→b∅q_1 \overset{b}{\to} \varnothingq1→b∅ , q23→bq23q_{23} \overset{b}{\to} q_{23}q23→bq23 , q23→a∅q_{23} \overset{a}{\to} \varnothingq23→a∅ ; q23q_{23}q23 accepts. The full DFA has 23=82^3 = 823=8 states; the other 5 are unreachable from the start state. Both machines recognize abnab^nabn , n≥0n \ge 0n≥0 .
[NFA - DFA equivalence] Over Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} : what are the ε\varepsilonε -closures of q1q_1q1 and of q4q_4q4 in this NFA?
ε\varepsilonε -closure of q1q_1q1 : {q1,q2,q3}\{q_1, q_2, q_3\}{q1,q2,q3} ; ε\ \varepsilon ε -closure of q4q_4q4 : {q4,q5}\{q_4, q_5\}{q4,q5} . q1→εq2→εq3q_1 \overset{\varepsilon}{\to} q_2 \overset{\varepsilon}{\to} q_3q1→εq2→εq3 , and q4→εq5q_4 \overset{\varepsilon}{\to} q_5q4→εq5 .
[NFA - DFA equivalence] Find a DFA equivalent to this NFA over Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} .
Two states: start q123q_{123}q123 , accepting q45q_{45}q45 ; 000 switches between them, 111 keeps the state. Start: ε\varepsilonε -closure of q1q_1q1 is q123q_{123}q123 . On 000 : q2→q5q_2 \to q_5q2→q5 , q3→q4q_3 \to q_4q3→q4 , closure q45q_{45}q45 . On 111 from q45q_{45}q45 : q4,q5→q4q_4, q_5 \to q_4q4,q5→q4 , closure q45q_{45}q45 . On 000 from q45q_{45}q45 : q5→q1q_5 \to q_1q5→q1 , closure q123q_{123}q123 .Both machines accept the strings with an odd number of 000 's.
[Exercises] Find an NFA over {0,1}\{0, 1\}{0,1} for the strings that start with 101101101 or end with 101101101 .
A start state with ε\varepsilonε -arrows to two machines: one reads 101101101 then loops on 0,10, 10,1 ; the other loops on 0,10, 10,1 then reads 101101101 .
[Exercises] Find an NFA over {a,b,c}\{a, b, c\}{a,b,c} for the strings whose last three symbols are the same.
A start state looping on a,b,ca, b, ca,b,c , then three branches reading aaaaaaaaa , bbbbbbbbb , ccccccccc into one accept state. Example: cabbbcabbbcabbb is accepted, aabaabaab is not.
[Exercises] Find an NFA over {a,b,c}\{a, b, c\}{a,b,c} for the strings that do not contain ccc or do not contain bbb . Examples: ε\varepsilonε , abaaabaabaaabaabaaaba , bbbbbb , acacac , acccaacccaaccca , cacacccacacccacacc .
ε\varepsilonε -arrows from the start state to two accept states: one loops on a,ba, ba,b , the other loops on a,ca, ca,c .
[Exercises] Find an NFA over {a,b,c}\{a, b, c\}{a,b,c} for the strings that start and end with aaa , contain exactly two aaa 's, and in which bbb 's and ccc 's alternate. Examples: aaaaaa , abaabaaba , acaacaaca , abcaabcaabca , acbcaacbcaacbca , abcbcbaabcbcbaabcbcba .
After the first aaa , branch into qbq_bqb and qcq_cqc ; qb→cqcq_b \overset{c}{\to} q_cqb→cqc , qc→bqbq_c \overset{b}{\to} q_bqc→bqb ; both go on aaa to the accept state. In qbq_bqb the next symbol must be ccc or the final aaa ; in qcq_cqc it must be bbb or the final aaa .
[Exercises] Find a DFA equivalent to this NFA over {0,1}\{0, 1\}{0,1} .
States q1,q123,q23,∅q_1, q_{123}, q_{23}, \varnothingq1,q123,q23,∅ ; all except ∅\varnothing∅ accept. q23q_{23}q23 stands for {q2,q3}\{q_2, q_3\}{q2,q3} . The ε\varepsilonε -closure of q2q_2q2 is {q2,q3}\{q_2, q_3\}{q2,q3} , so q1→1q23q_1 \overset{1}{\to} q_{23}q1→1q23 and q1→0q123q_1 \overset{0}{\to} q_{123}q1→0q123 .
[Exercises] Find a DFA equivalent to this NFA over {0,1}\{0, 1\}{0,1} .
States q1,q2,q34,q4,q14,∅q_1, q_2, q_{34}, q_4, q_{14}, \varnothingq1,q2,q34,q4,q14,∅ ; accepting q34,q4,q14q_{34}, q_4, q_{14}q34,q4,q14 . q34q_{34}q34 stands for {q3,q4}\{q_3, q_4\}{q3,q4} . From q34q_{34}q34 : on 111 only q3→q4q_3 \to q_4q3→q4 , on 000 only q4→{q1,q4}q_4 \to \{q_1, q_4\}q4→{q1,q4} .
[Exercises] Find a DFA equivalent to this NFA over {a,b}\{a, b\}{a,b} . Which language is it?
Two states: q1q_1q1 loops on aaa , q1→bq123q_1 \overset{b}{\to} q_{123}q1→bq123 , q123q_{123}q123 accepts and loops on a,ba, ba,b . The language: strings containing bbb . On bbb , q1q_1q1 reaches q1q_1q1 and q2q_2q2 , and the ε\varepsilonε -closure of q2q_2q2 adds q3q_3q3 .
[Exercises] Find a DFA equivalent to this NFA over {0,1}\{0, 1\}{0,1} .
States q1,q24,q13,∅q_1, q_{24}, q_{13}, \varnothingq1,q24,q13,∅ ; all except ∅\varnothing∅ accept. The ε\varepsilonε -closure of q2q_2q2 is {q2,q4}\{q_2, q_4\}{q2,q4} . From q24q_{24}q24 : on 000 , q4q_4q4 reaches q1q_1q1 and q3q_3q3 ; on 111 , q4q_4q4 reaches q2q_2q2 , closure q24q_{24}q24 .
[Exercises] Find an NFA over {0,1}\{0, 1\}{0,1} for the strings that start with 010101 , end with 101010 , and have length at least 5.
Read 010101 , then one symbol, then loop on 0,10, 10,1 , then read 101010 . The one forced symbol in the middle gives the minimum length 2+1+2=52 + 1 + 2 = 52+1+2=5 .
[Exercises] Find an NFA over {0,1}\{0, 1\}{0,1} for the strings that start with 000 and have odd length, or start with 111 and have length at most 3.
q1→0q_1 \overset{0}{\to}q1→0 a two-state cycle (accepting after odd length); q1→1q_1 \overset{1}{\to}q1→1 a chain of three accept states.
[Exercises] Find an NFA over {a,b}\{a, b\}{a,b} for the strings that start and end with aaa , have length at least 2, contain aaa 's only in runs of two or more, and do not contain bbbbbb .
s→at→afs \overset{a}{\to} t \overset{a}{\to} fs→at→af , with fff accepting, fff looping on aaa , and f→bsf \overset{b}{\to} sf→bs . Example: aaaaaa , aaabaaaaabaaaaabaa are accepted; abaabaaba , aabbaaaabbaaaabbaa are not.
[Exercises] Find an NFA over {a,b,c}\{a, b, c\}{a,b,c} for the strings that do not contain aaaaaa , bbbbbb or cccccc . Examples: ε\varepsilonε , aaa , caccaccac , babababababa , abcbcabacbabcbcabacbabcbcabacb .
Accept states qa,qb,qcq_a, q_b, q_cqa,qb,qc for the last symbol read; each xxx leads to qxq_xqx , except that qxq_xqx has no arrow for xxx . The start state must also be accepting, so that ε\varepsilonε is accepted; the book's drawing leaves it non-accepting.
[Exercises] Find an NFA over {0,1}\{0, 1\}{0,1} for the strings that do not contain 111111 and contain 000 's only in runs of two or three. Examples: ε\varepsilonε , 111 , 000000 , 100010001000 , 001000100100010010001 , 100010011000100110001001 .
Alternate between a single 111 and a run 000000 or 000000000 , starting with either. Left accept state: the next symbol must be 111 . Right accept state: the next symbols must be 000000 or 000000000 . The start reaches both by ε\varepsilonε .
[Exercises] Find an NFA over {0,1}\{0, 1\}{0,1} for the strings that contain 111111111 or 000000000 .
A start state looping on 0,10, 10,1 , two branches reading 000000000 and 111111111 , and an accept state looping on 0,10, 10,1 .