Ch.1: Finite Automata

Week 1 of the book "Automata, Formal Languages, and Turing Machines" by Emre Sermutlu (2020) 1.1. Introduction 1.2. The Formal Definition of DFA

39 flashcards · Computer Science · by lakesare

Part of Textbooks › Automata, Formal Languages, and Turing Machines (Emre Sermutlu) · 14 courses

1. [Introduction] A vending machine takes only 5-dollar and 10-dollar bills and sells a product priced 15 dollars. Modelled as an automaton, what do the states stand for, and which state accepts?

   States = the amount inserted so far: 0, 5, 10, 15 and ∞\infty∞ (more than 15). The accept state is 15. Each arrow is labelled with the bill inserted. If the input ends in state 15, the machine gives the product; otherwise it returns the money.

2. [Introduction] What is an alphabet?

   A finite set of symbols. Example: Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} or Σ={a,b,c}\Sigma = \{a, b, c\}Σ={a,b,c} .

3. [Introduction] What is a string over an alphabet Σ\SigmaΣ ?

   A finite sequence of symbols from Σ\SigmaΣ . Example: 010001010001010001 is a string of length 6 over {0,1}\{0, 1\}{0,1} .

4. [Introduction] The string of length zero is called the empty string.

   It is written ε\varepsilonε .

5. [Introduction] What is a language?

   A set of strings. Example: {w∣w ends with 01}\{w \mid w \text{ ends with } 01\}{w∣w ends with 01} over {0,1}\{0, 1\}{0,1} , which contains 01,101,0001,…01, 101, 0001, \dots01,101,0001,…

6. [Introduction] How does the state diagram of a deterministic finite automaton (DFA) show its parts?

   States Circles, usually labelled q1,q2,…q_1, q_2, \dotsq1​,q2​,… Start state The state with an arrow coming from no other state. Accept states Double circles. Transitions Arrows between states, labelled with input symbols. Example: an arrow from q1q_1q1​ to q2q_2q2​ labelled 111 means: in state q1q_1q1​ , reading 111 moves the DFA to q2q_2q2​ .

7. [Introduction] In the state diagram of a DFA, how many arrows leave each state?

   Exactly one arrow for each symbol of the alphabet. One arrow may carry several symbols, e.g. an arrow labelled 0,10, 10,1 .

8. [Introduction] What is the input of a DFA, and what is its output?

   Input: a string over its alphabet. Output: accept or reject. The DFA starts in the start state, follows one arrow per symbol, and accepts if and only if it is in an accept state after the last symbol.

9. [Introduction] Does this DFA accept 100001000010000 ? Does it accept 010010010 ?

   100001000010000 : accept. 010010010 : reject. 100001000010000 : q1→q2→q3→q3→q3→q3q_1 \to q_2 \to q_3 \to q_3 \to q_3 \to q_3q1​→q2​→q3​→q3​→q3​→q3​ , and q3q_3q3​ is an accept state. 010010010 : q1→q4→q4→q5q_1 \to q_4 \to q_4 \to q_5q1​→q4​→q4​→q5​ , and q5q_5q5​ is not an accept state.

10. [Introduction] Which binary strings does this DFA accept?

    Strings that start with 111 and have length at least 2, and strings 000 followed only by 111 's. Example: it accepts 0,01,011,10,11,100000, 01, 011, 10, 11, 100000,01,011,10,11,10000 and rejects 1,00,010,00011, 00, 010, 00011,00,010,0001 .

11. [Introduction] In a DFA, which states are reject states?

    All states that are not accept states.

12. [Introduction] A reject state that the DFA can never leave is called a trap state.

    Every transition from a trap state goes back to the trap state itself, so once the DFA enters it, the string is rejected. Example: a state q5q_5q5​ with one arrow from q5q_5q5​ to q5q_5q5​ labelled 0,10, 10,1 , where q5q_5q5​ is not an accept state.

13. [Introduction] In the transition table of a DFA, what is the entry in row qqq , column aaa , and how are the start state and accept states marked?

    The entry is the next state from qqq on symbol aaa . The start state is marked →\to→ , accept states ⊚\circledcirc⊚ . Example: in this table, from q4q_4q4​ on input 000 the DFA moves to q5q_5q5​ .

14. [Introduction] Given the current state and an input symbol, the next state of a DFA is determined uniquely. That is why its computation is called deterministic.

15. [The Formal Definition of DFA] A deterministic 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, the states. Example: Q={q1,q2}Q = \{q_1, q_2\}Q={q1​,q2​} . Σ\SigmaΣ A finite set, the alphabet. Example: Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} . δ:Q×Σ→Q\delta : Q \times \Sigma \to Qδ:Q×Σ→Q The transition function: δ(q,a)\delta(q, a)δ(q,a) is the next state from state qqq on symbol aaa . Example: δ(q1,1)=q2\delta(q_1, 1) = q_2δ(q1​,1)=q2​ . q0∈Qq_0 \in Qq0​∈Q The start state. Example: q0=q1q_0 = q_1q0​=q1​ . F⊆QF \subseteq QF⊆Q The set of accept states. Example: F={q1}F = \{q_1\}F=…

16. [The Formal Definition of DFA] Why does a DFA have exactly one arrow leaving each state for each symbol?

    Because the transition function δ:Q×Σ→Q\delta : Q \times \Sigma \to Qδ:Q×Σ→Q assigns to each pair (q,a)(q, a)(q,a) exactly one state δ(q,a)\delta(q, a)δ(q,a) .

17. [The Formal Definition of DFA] MMM is a DFA and AAA is the set of all strings that MMM accepts. What do L(M)=AL(M) = AL(M)=A and " MMM recognizes AAA " mean?

    Both say: AAA is the language of MMM , the set of all strings MMM accepts. MMM must accept every string in AAA and reject every string not in AAA .

18. [The Formal Definition of DFA] Write this DFA over Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} as a 5-tuple (Q,Σ,δ,q0,F)(Q, \Sigma, \delta, q_0, F)(Q,Σ,δ,q0​,F) .

    Q={q1,q2}Q = \{q_1, q_2\}Q={q1​,q2​} , δ(q1,0)=δ(q1,1)=q2\delta(q_1, 0) = \delta(q_1, 1) = q_2δ(q1​,0)=δ(q1​,1)=q2​ , δ(q2,0)=δ(q2,1)=q1\delta(q_2, 0) = \delta(q_2, 1) = q_1δ(q2​,0)=δ(q2​,1)=q1​ , q0=q1q_0 = q_1q0​=q1​ , F={q2}F = \{q_2\}F={q2​} .

19. [The Formal Definition of DFA] Which language over {0,1}\{0, 1\}{0,1} does this DFA recognize?

    All strings of odd length. Every symbol switches the state, so the DFA is in q2q_2q2​ exactly when it has read an odd number of symbols.Example: it accepts 0,1,1010, 1, 1010,1,101 and rejects ε,00,10\varepsilon, 00, 10ε,00,10 .

20. [The Formal Definition of DFA] Which language over {0,1}\{0, 1\}{0,1} does this DFA recognize?

    All strings with an even number of 111 's. A 000 does not change the state; a 111 switches between q1q_1q1​ and q2q_2q2​ .Example: it accepts ε,00,0110\varepsilon, 00, 0110ε,00,0110 and rejects 1,01001, 01001,0100 .

21. [The Formal Definition of DFA] Which language over {0,1}\{0, 1\}{0,1} does this DFA recognize?

    Strings that start with 111 and end with 000 . A first symbol 000 leads to a trap state. After a first 111 , the DFA is in the accept state exactly when the last symbol read is 000 .Example: it accepts 10,1100,101010, 1100, 101010,1100,1010 and rejects 0110,101,10110, 101, 10110,101,1 .

22. [The Formal Definition of DFA] A DFA over Σ={a,b,c}\Sigma = \{a, b, c\}Σ={a,b,c} has this transition table. Which language does it recognize?

    Strings that contain neither ababab nor bababa , i.e. between an aaa and a bbb there is always at least one ccc . q4q_4q4​ is a trap state. q2q_2q2​ : last symbol aaa ; q3q_3q3​ : last symbol bbb ; q1q_1q1​ : start, or last symbol ccc .Example: it accepts aacbbaacbbaacbb and acbacbacb , and rejects cabccabccabc .

23. [The Formal Definition of DFA] Give a DFA over {0,1}\{0, 1\}{0,1} that recognizes L={w∣the length of w is 2 modulo 5}L = \{w \mid \text{the length of } w \text{ is } 2 \text{ modulo } 5\}L={w∣the length of w is 2 modulo 5} .

    Five states q0,…,q4q_0, \dots, q_4q0​,…,q4​ in a cycle, every arrow labelled 0,10, 10,1 ; start q0q_0q0​ , only accept state q2q_2q2​ . The DFA is in qiq_iqi​ exactly when the length read so far is iii modulo 5. Counting only the 000 's (or only the 111 's) works the same way, with a loop on the other symbol at each state.

24. [The Formal Definition of DFA] Give a DFA over {0,1}\{0, 1\}{0,1} that recognizes L={w∣w ends with 01}L = \{w \mid w \text{ ends with } 01\}L={w∣w ends with 01} .

    Three states: start, "ends with 000 ", and accept "ends with 010101 ". A 000 from any state leads to the middle state. A 111 leads from the middle state to the accept state, and from the other two states to the start state.

25. [The Formal Definition of DFA] A DFA over {0,1}\{0, 1\}{0,1} recognizes the strings that end with 010101 , using three states.What does the DFA know about the string read so far in each of its three states?

    Start: the string does not end with 000 or 010101 . Middle: it ends with 000 . Accept: it ends with 010101 . Example: on 100110011001 the states are start, start, middle, middle, accept.

26. [Exercises] Which language over {0,1}\{0, 1\}{0,1} does this DFA recognize?

    Strings that start and end with the same symbol. The left branch handles a first symbol 000 , the right branch a first symbol 111 ; in each branch the accept state is the one reached by that same symbol.Example: it accepts 0,0110,1010, 0110, 1010,0110,101 and rejects ε,01,110\varepsilon, 01, 110ε,01,110 .

27. [Exercises] Which language over {0,1}\{0, 1\}{0,1} does this DFA recognize?

    Strings that do not contain 111111111111 . q1,…,q4q_1, \dots, q_4q1​,…,q4​ count the 111 's at the end of the string (0 to 3); a 000 resets the count; a fourth consecutive 111 leads to the trap state q5q_5q5​ .Example: it accepts 111011111101111110111 and rejects 011110011110011110 .

28. [Exercises] Which language over {0,1}\{0, 1\}{0,1} does this DFA recognize?

    Strings that contain 101010 and end with 111 . Equivalent descriptions: the string contains 1,0,11, 0, 11,0,1 in this order (not necessarily consecutively) and ends with 111 ; or it changes symbols at least twice and ends with 111 .Example: it accepts 101,0011001101, 0011001101,0011001 and rejects 0111,10100111, 10100111,1010 .

29. [Exercises] Which language over {0,1}\{0, 1\}{0,1} does this DFA recognize?

    Strings that contain neither 000000 nor 111111 , i.e. strings whose symbols alternate. q2q_2q2​ : last symbol 000 ; q3q_3q3​ : last symbol 111 ; a repeated symbol leads to the trap state q4q_4q4​ .Example: it accepts ε,0,1010\varepsilon, 0, 1010ε,0,1010 and rejects 011001100110 .

30. [Exercises] Which language over {0,1}\{0, 1\}{0,1} does this DFA recognize?

    Strings whose second symbol from the end is 111 , i.e. strings ending with 101010 or 111111 . The four states record the last two symbols: start (ends with 000000 , or 000 , or empty), middle ( 010101 or 111 ), top accept ( 101010 ), bottom accept ( 111111 ).Example: it accepts 10,001110, 001110,0011 and rejects 1,1011, 1011,101 .

31. [Exercises] Which language over {0,1}\{0, 1\}{0,1} does this DFA recognize?

    Strings in which every 111 is in a block of exactly two or exactly four consecutive 111 's. The bottom row counts the 111 's of the current block; a 000 after one or three 111 's, or a fifth 111 , leads to the trap state at the top.Example: it accepts ε,0110,11011110\varepsilon, 0110, 11011110ε,0110,11011110 and rejects 1,01110,1111111, 01110, 1111111,01110,111111 .

32. [Exercises] This DFA is over Σ={a,b,c}\Sigma = \{a, b, c\}Σ={a,b,c} . Which language does it recognize?

    Strings with kkk aaa 's, mmm bbb 's and nnn ccc 's such that k+2m+3n≡2(mod4)k + 2m + 3n \equiv 2 \pmod 4k+2m+3n≡2(mod4) . The DFA is in qiq_iqi​ when k+2m+3n≡i(mod4)k + 2m + 3n \equiv i \pmod 4k+2m+3n≡i(mod4) : an aaa moves from qiq_iqi​ to qi+1q_{i+1}qi+1​ , a bbb to qi+2q_{i+2}qi+2​ , a ccc to qi+3q_{i+3}qi+3​ (indices mod 4).Example: bbb and aaaaaa are accepted ( 2≡22 \equiv 22≡2 ); acacac is rejected ( 1+3=4≡01 + 3 = 4 \equiv 01+3=4≡0 ).

33. [Exercises] Give a DFA over {a,b}\{a, b\}{a,b} that recognizes the strings containing exactly two aaa 's.

    States 0,1,20, 1, 20,1,2 , "more" count the aaa 's; each has a loop on bbb ; only state 222 accepts. "more" is a trap state for strings with three or more aaa 's.

34. [Exercises] A DFA over {a,b}\{a, b\}{a,b} with states 0,1,20, 1, 20,1,2 , "more" counts the aaa 's (loops on bbb , "more" loops on a,ba, ba,b ); with accept state 222 only, it recognizes the strings with exactly two aaa 's.Which accept states make the same DFA recognize the strings with at least two aaa 's, and with at most two aaa 's?

    At least two: accept 222 and "more". At most two: accept 0,1,20, 1, 20,1,2 . At least two aaa 's. At most two aaa 's.

35. [Exercises] Give a DFA over {a,b}\{a, b\}{a,b} that recognizes L={anbm∣n,m≥1}L = \{a^n b^m \mid n, m \ge 1\}L={anbm∣n,m≥1} .

    Start, then a state for the aaa 's (loop aaa ), then an accept state for the bbb 's (loop bbb ); every other transition goes to a trap state. A first bbb , or an aaa after a bbb , leads to the trap state. Example: it accepts ab,aabbbab, aabbbab,aabbb and rejects b,abab, abab,aba .

36. [Exercises] Give a DFA over {0,1}\{0, 1\}{0,1} that recognizes the strings that contain 000000000000 and end with 111111 .

    Four states count consecutive 000 's until 000000000000 appears (a 111 resets the count); after that, three states check whether the string ends with 111111 . Left part: start and the states after 000 , 000000 , 000000000 . Right part (after 000000000000 ): last symbol 000 , last symbol a single 111 , and the accept state "ends with 111111 ".

37. [Exercises] Give a DFA over {a,b,c}\{a, b, c\}{a,b,c} that recognizes the strings that do not contain aaaaaa , bbbbbb or cccccc .

    An accepting start state, accepting states qa,qb,qcq_a, q_b, q_cqa​,qb​,qc​ for "last symbol is aaa , bbb , ccc ", and a trap state. From qxq_xqx​ , the symbol xxx leads to the trap state and any other symbol yyy leads to qyq_yqy​ . Example: it accepts ε,abcbacb\varepsilon, abcbacbε,abcbacb and rejects abbaabbaabba .

38. [Exercises] Give a DFA over {0,1}\{0, 1\}{0,1} that recognizes the strings that contain 111111111 or 000000000 .

    Two chains count the current run of 111 's and of 000 's (lengths 1 and 2); a third equal symbol leads to an accept state with a loop on 0,10, 10,1 . A symbol that differs from the current run moves to the length-1 state of the other chain. Example: it accepts 010001101000110100011 and rejects 011001001100100110010 .

39. [Exercises] Give a DFA over {0,1}\{0, 1\}{0,1} that recognizes the strings with one or two 000 's among their first three symbols.

    A tree over the first three symbols, with an accepting state (loop 0,10, 10,1 ) for prefixes that already contain both symbols, and a trap state for 000000000 and 111111111 . Once the first two symbols are 010101 or 101010 , the third symbol does not matter. The prefixes 000 and 000000 are accepted too.