Ch.3: Regular Languages

Week 3 of the book "Automata, Formal Languages, and Turing Machines" by Emre Sermutlu (2020) 3.1. Operations on Regular Languages 3.2. Closure Properties of Regular Languages

44 flashcards · Computer Science · by lakesare

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

  1. [Operations on Regular Languages] When is a language called regular?

    When some finite automaton (a DFA or an NFA) recognizes it. DFAs and NFAs recognize the same languages, so either kind of machine may be used to show that a language is regular.Example: over Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} , {w∣w contains an even number of 1’s}\{w \mid w \text{ contains an even number of 1's}\}{w∣w contains an even number of 1’s} is regular.

  2. [Operations on Regular Languages] Over Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} , why is {w∣w contains an even number of 1’s}\{w \mid w \text{ contains an even number of 1's}\}{w∣w contains an even number of 1’s} regular?

    A 2-state DFA recognizes it: the state records whether the number of 1's read so far is even ( q0q_0q0​ ) or odd ( q1q_1q1​ ). Each 1 switches the state, each 0 keeps it.

  3. [Operations on Regular Languages] Over Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} , is {w∣w contains a prime number of 1’s}\{w \mid w \text{ contains a prime number of 1's}\}{w∣w contains a prime number of 1’s} regular?

    No. A finite automaton has finitely many states, but deciding whether the number of 1's is prime requires the exact number of 1's, which can be arbitrarily large.

  4. [Operations on Regular Languages] Over Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} , is {w∣w contains an equal number of 1’s and 0’s}\{w \mid w \text{ contains an equal number of 1's and 0's}\}{w∣w contains an equal number of 1’s and 0’s} regular?

    No. A machine for it must store the difference between the number of 1's and the number of 0's read so far. This difference can be any integer, and a finite automaton has only finitely many states.

  5. [Operations on Regular Languages] What is the union A∪BA \cup BA∪B of two languages AAA and BBB ?

    A∪B={w∣w∈A or w∈B}\boldsymbol{A \cup B = \{w \mid w \in A \text{ or } w \in B\}}A∪B={w∣w∈A or w∈B} Example: {a,ab}∪{bb,abba}={a,ab,bb,abba}\{a, ab\} \cup \{bb, abba\} = \{a, ab, bb, abba\}{a,ab}∪{bb,abba}={a,ab,bb,abba} .

  6. [Operations on Regular Languages] What is the concatenation A∘BA \circ BA∘B of two languages AAA and BBB ?

    A∘B={vw∣v∈A and w∈B}\boldsymbol{A \circ B = \{vw \mid v \in A \text{ and } w \in B\}}A∘B={vw∣v∈A and w∈B} Each string of A∘BA \circ BA∘B is a string of AAA followed by a string of BBB . The operator ∘\circ∘ is usually omitted: ABABAB .Example: {a,ab}∘{bb,abba}={abb,aabba,abbb,ababba}\{a, ab\} \circ \{bb, abba\} = \{abb, aabba, abbb, ababba\}{a,ab}∘{bb,abba}={abb,aabba,abbb,ababba} .

  7. [Operations on Regular Languages] What is the star A∗A^*A∗ of a language AAA ?

    A∗={w1w2…wk∣k≥0 and each wi∈A}\boldsymbol{A^* = \{w_1 w_2 \dots w_k \mid k \ge 0 \text{ and each } w_i \in A\}}A∗={w1​w2​…wk​∣k≥0 and each wi​∈A} All concatenations of any number of strings of AAA , repetitions allowed.Example: {ab}∗={ε,ab,abab,ababab,… }\{ab\}^* = \{\varepsilon, ab, abab, ababab, \dots\}{ab}∗={ε,ab,abab,ababab,…} .

  8. [Operations on Regular Languages] Why does A∗A^*A∗ contain ε\varepsilonε for every language AAA ?

    k=0k = 0k=0 is allowed in A∗={w1…wk∣k≥0, wi∈A}A^* = \{w_1 \dots w_k \mid k \ge 0, \ w_i \in A\}A∗={w1​…wk​∣k≥0, wi​∈A} , and the concatenation of zero strings is ε\varepsilonε . Example: ∅∗={ε}\emptyset^* = \{\varepsilon\}∅∗={ε} .

  9. [Operations on Regular Languages] C={a,bb}C = \{a, bb\}C={a,bb} . Which strings of C∗C^*C∗ have length at most 3?

    ε, a, aa, bb, aaa, abb, bba\boldsymbol{\varepsilon, \ a, \ aa, \ bb, \ aaa, \ abb, \ bba}ε, a, aa, bb, aaa, abb, bba babbabbab is not in C∗C^*C∗ : it cannot be split into pieces aaa and bbbbbb .

  10. [Operations on Regular Languages] What is the precedence of the operations union, concatenation and star?

    Star first, then concatenation, then union. Example: AB∗A∪C∗AB^*A \cup C^*AB∗A∪C∗ means (A∘(B∗)∘A)∪(C∗)\big(A \circ (B^*) \circ A\big) \cup (C^*)(A∘(B∗)∘A)∪(C∗) .

  11. [Operations on Regular Languages] A={1}A = \{1\}A={1} , B={0}B = \{0\}B={0} , C={11}C = \{11\}C={11} . Which strings does AB∗A∪C∗AB^*A \cup C^*AB∗A∪C∗ contain?

    Strings 10…011 0 \dots 0 110…01 (a 1, any number of 0's, a 1), and strings of an even number of 1's with no 0's. Example: 111111 , 101101101 , 100011000110001 , ε\varepsilonε , 111111111111 are in it; 000 , 111111111 , 101110111011 are not.

  12. [Closure Properties of Regular Languages] A class of languages is closed under an operation if applying the operation to languages of the class always gives a language of the class.

    Example: the regular languages are closed under union: if AAA and BBB are regular, so is A∪BA \cup BA∪B .

  13. [Closure Properties of Regular Languages] Under which three basic operations on languages is the class of regular languages closed?

    Union If AAA and BBB are regular, so is A∪BA \cup BA∪B . Example: {w∣w contains 11}∪{w∣w does not contain 000}\{w \mid w \text{ contains } 11\} \cup \{w \mid w \text{ does not contain } 000\}{w∣w contains 11}∪{w∣w does not contain 000} is regular. Concatenation If AAA and BBB are regular, so is A∘BA \circ BA∘B . Example: {w∣w contains 010}∘{w∣w contains an even number of 0’s}\{w \mid w \text{ contains } 010\} \circ \{w \mid w \text{ contains an even number of 0's}\}{w∣w contains 010}∘{w∣w…

  14. [Closure Properties of Regular Languages] To show that A∪BA \cup BA∪B is regular, we build a DFA from a DFA MAM_AMA​ for AAA and a DFA MBM_BMB​ for BBB . Why must the new DFA run MAM_AMA​ and MBM_BMB​ simultaneously?

    A DFA reads its input once, from left to right, so it cannot first run MAM_AMA​ on the input and then run MBM_BMB​ on it. At the start the machine does not know whether the input belongs to AAA or to BBB , so it follows both machines symbol by symbol.

  15. [Closure Properties of Regular Languages] MAM_AMA​ and MBM_BMB​ are DFAs recognizing AAA and BBB .How is the product DFA recognizing A∪BA \cup BA∪B built?

    States All pairs (p,q)(p, q)(p,q) with ppp a state of MAM_AMA​ and qqq a state of MBM_BMB​ . Example: q1xq_{1x}q1x​ stands for the pair (q1,qx)(q_1, q_x)(q1​,qx​) . Start state The pair of the two start states. Accept states The pairs (p,q)(p, q)(p,q) where ppp is an accept state of MAM_AMA​ or qqq is an accept state of MBM_BMB​ . Transitions On symbol aaa , the pair (p,q)(p, q)(p,q) goes to (p′,q′)(p', q')(p′,q′) , where MAM_AMA​ goes from ppp to p′p'p′ on aaa and MBM_BMB​ goes…

  16. [Closure Properties of Regular Languages] MAM_AMA​ is a DFA with mmm states and MBM_BMB​ a DFA with nnn states. How many states does the product DFA for A∪BA \cup BA∪B have?

    mn\boldsymbol{mn}mn One state for each pair (state of MAM_AMA​ , state of MBM_BMB​ ).Example: m=2m = 2m=2 , n=3n = 3n=3 gives 6 states.

  17. [Closure Properties of Regular Languages] The product DFA for A∪BA \cup BA∪B has as states the pairs (p,q)(p, q)(p,q) of a state ppp of MAM_AMA​ and a state qqq of MBM_BMB​ , and runs both machines in parallel.What do you change to make it recognize A∩BA \cap BA∩B ?

    The accept states: only pairs (p,q)(p, q)(p,q) where both ppp and qqq are accept states. This proves that the regular languages are also closed under intersection.

  18. [Closure Properties of Regular Languages] Two DFAs (only the arrows leaving the start states are shown): In the product DFA for A∪BA \cup BA∪B , where does q1xq_{1x}q1x​ go on 1 and on 0, and which of its six states q1x,…,q3yq_{1x}, \dots, q_{3y}q1x​,…,q3y​ are accept states?

    q1x→q2xq_{1x} \to q_{2x}q1x​→q2x​ on 1, q1x→q3yq_{1x} \to q_{3y}q1x​→q3y​ on 0; accept states q2x,q1y,q2y,q3yq_{2x}, q_{1y}, q_{2y}, q_{3y}q2x​,q1y​,q2y​,q3y​ . A pair is accepting when q2q_2q2​ or qyq_yqy​ is one of its components.

  19. [Closure Properties of Regular Languages] How do you build an NFA recognizing A∪BA \cup BA∪B from NFAs (or DFAs) for AAA and for BBB ?

    Add a new start state with ε\varepsilonε -transitions to the two old start states; the old accept states stay accept states. The two machines then compute in parallel.

  20. [Closure Properties of Regular Languages] Over Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} : A={w∣number of 1’s in w is a multiple of 2}A = \{w \mid \text{number of 1's in } w \text{ is a multiple of 2}\}A={w∣number of 1’s in w is a multiple of 2} , B={w∣number of 1’s in w is a multiple of 3}B = \{w \mid \text{number of 1's in } w \text{ is a multiple of 3}\}B={w∣number of 1’s in w is a multiple of 3} , with DFAs: Describe the product DFA for A∪BA \cup BA∪B .

    6 states qijq_{ij}qij​ ( iii = number of 1's mod 2, jjj = mod 3); accept states q00,q01,q02,q10q_{00}, q_{01}, q_{02}, q_{10}q00​,q01​,q02​,q10​ . Every 0 keeps the state; every 1 (all arrows in the middle) goes from qijq_{ij}qij​ to qi+1 mod 2, j+1 mod 3q_{i+1 \bmod 2, \ j+1 \bmod 3}qi+1mod2, j+1mod3​ .

  21. [Closure Properties of Regular Languages] Over Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} : A={w∣number of 1’s in w is a multiple of 2}A = \{w \mid \text{number of 1's in } w \text{ is a multiple of 2}\}A={w∣number of 1’s in w is a multiple of 2} , B={w∣number of 1’s in w is a multiple of 3}B = \{w \mid \text{number of 1's in } w \text{ is a multiple of 3}\}B={w∣number of 1’s in w is a multiple of 3} .Give an NFA for A∪BA \cup BA∪B built from a 2-state DFA for AAA and a 3-state DFA for BBB .

    A new start state with ε\varepsilonε -transitions to the start states of the two DFAs. From machines with mmm and nnn states, this NFA has m+n+1m + n + 1m+n+1 states, the product DFA mnmnmn ; here 6 and 6, but the NFA has far fewer arrows.

  22. [Closure Properties of Regular Languages] Over Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} : A={w∣w ends with 11}A = \{w \mid w \text{ ends with } 11\}A={w∣w ends with 11} , B={w∣w contains an odd number of 1’s}B = \{w \mid w \text{ contains an odd number of 1's}\}B={w∣w contains an odd number of 1’s} .Which split of 101101001100110110100110011011010011001 into a string of AAA followed by a string of BBB works: 1011∣0100110011011 \mid 0100110011011∣010011001 or 1011010011∣0011011010011 \mid 0011011010…

    1011010011∣0011011010011 \mid 0011011010011∣001 . 010011001010011001010011001 contains four 1's, so it is not in BBB ; 001001001 contains one 1.

  23. [Closure Properties of Regular Languages] To recognize A∘BA \circ BA∘B , why is it wrong to run the machine for AAA and switch to the machine for BBB as soon as the machine for AAA first enters an accept state?

    The correct split point may come at a later visit to an accept state. So the machine must be able to switch whenever the machine for AAA is in an accept state, which is easy with an NFA and ε\varepsilonε -transitions.Example: A={w∣w ends with 11}A = \{w \mid w \text{ ends with } 11\}A={w∣w ends with 11} , B={w∣w has an odd number of 1’s}B = \{w \mid w \text{ has an odd number of 1's}\}B={w∣w has an odd number of 1’s} , input 101101001100110110100110011011010011001 : switching after 1011101…

  24. [Closure Properties of Regular Languages] How do you build an NFA recognizing A∘BA \circ BA∘B from NFAs for AAA and for BBB ?

    Add ε\varepsilonε -transitions from every accept state of the machine for AAA to the start state of the machine for BBB ; those accept states become non-accepting. The start state is that of the machine for AAA , the accept states are those of the machine for BBB .

  25. [Closure Properties of Regular Languages] Over Σ={a,b,c}\Sigma = \{a, b, c\}Σ={a,b,c} : A={aa,bb}A = \{aa, bb\}A={aa,bb} , B={ac,bc}B = \{ac, bc\}B={ac,bc} .Give an NFA for A∘BA \circ BA∘B . Which language is A∘BA \circ BA∘B ?

    A∘B={aaac,aabc,bbac,bbbc}\boldsymbol{A \circ B = \{aaac, aabc, bbac, bbbc\}}A∘B={aaac,aabc,bbac,bbbc} The accept states q3q_3q3​ and q5q_5q5​ of the NFA for AAA get ε\varepsilonε -transitions to the start state q6q_6q6​ of the NFA for BBB and stop being accept states.

  26. [Closure Properties of Regular Languages] Over Σ={a,b,c}\Sigma = \{a, b, c\}Σ={a,b,c} : A={w∣w starts with abc}A = \{w \mid w \text{ starts with } abc\}A={w∣w starts with abc} , B={w∣w ends with cba}B = \{w \mid w \text{ ends with } cba\}B={w∣w ends with cba} .Give an NFA for A∘BA \circ BA∘B . Is abcbaabcbaabcba in A∘BA \circ BA∘B ?

    A∘BA \circ BA∘B = the strings abc x cbaabc \, x \, cbaabcxcba ( xxx any string), so abcba∉A∘Babcba \notin A \circ Babcba∈/A∘B . abcbaabcbaabcba starts with abcabcabc and ends with cbacbacba , but has length 5, and every string of A∘BA \circ BA∘B has length at least 6.

  27. [Closure Properties of Regular Languages] How do you build an NFA recognizing A∗A^*A∗ from an NFA for AAA ?

    A new accepting start state with ε\varepsilonε to the old start state, and ε\varepsilonε from every accept state back to the old start state. The old accept states stay accept states.

  28. [Closure Properties of Regular Languages] An NFA for A∗A^*A∗ is built from an NFA for AAA by adding ε\varepsilonε -transitions from the accept states back to the start state.Why add a new accepting start state, instead of making the old start state accepting?

    The NFA must accept ε\varepsilonε , but making the old start state accepting can make the NFA accept strings that are not in A∗A^*A∗ . The old start state may be reached again after reading symbols, and those strings would then be accepted.

  29. [Closure Properties of Regular Languages] Over Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} : A={w∣w ends with 00}A = \{w \mid w \text{ ends with } 00\}A={w∣w ends with 00} . This NFA was meant to recognize A∗A^*A∗ : Which short string shows that it is wrong, and how is it fixed?

    111 : the NFA accepts it, but 1∉A∗1 \notin A^*1∈/A∗ . Fix: a new accepting start state with an ε\varepsilonε -transition to q0q_0q0​ , and q0q_0q0​ non-accepting. With q0q_0q0​ accepting and its loop on 0, 1, the wrong NFA accepts every string.

  30. [Closure Properties of Regular Languages] Over Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} , A={w∣w ends with 00}A = \{w \mid w \text{ ends with } 00\}A={w∣w ends with 00} . What is A∗A^*A∗ ?

    A∗={ε}∪A\boldsymbol{A^* = \{\varepsilon\} \cup A}A∗={ε}∪A A concatenation of one or more strings ending with 000000 ends with 000000 .Example: the same holds for A={w∣w ends with 11 or 000}A = \{w \mid w \text{ ends with } 11 \text{ or } 000\}A={w∣w ends with 11 or 000} .

  31. [Closure Properties of Regular Languages] Over Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} : A={w∣w contains 11}A = \{w \mid w \text{ contains } 11\}A={w∣w contains 11} , B={w∣w does not contain 000}B = \{w \mid w \text{ does not contain } 000\}B={w∣w does not contain 000} .Give an NFA for A∪BA \cup BA∪B .

    A new start state with ε\varepsilonε -transitions to a DFA for AAA ( a1,a2,a3a_1, a_2, a_3a1​,a2​,a3​ ) and a DFA for BBB ( b1,b2,b3b_1, b_2, b_3b1​,b2​,b3​ ). aia_iai​ : the last i−1i - 1i−1 symbols are 1's ( a3a_3a3​ : 111111 was seen). bib_ibi​ : the string read ends with i−1i - 1i−1 zeros.

  32. [Closure Properties of Regular Languages] An NFA for {w∣w does not contain 000}\{w \mid w \text{ does not contain } 000\}{w∣w does not contain 000} has states b1,b2,b3b_1, b_2, b_3b1​,b2​,b3​ (the string read ends with 0, 1 or 2 zeros). Why does it need no state for " 000000000 was read"?

    In an NFA, a missing transition means that branch of the computation stops and does not accept. A DFA must have a transition for every symbol, so the DFA has an extra trap state that b3b_3b3​ goes to on 0.

  33. [Closure Properties of Regular Languages] Over Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} : A={w∣w contains 010}A = \{w \mid w \text{ contains } 010\}A={w∣w contains 010} , B={w∣w contains an even number of 0’s}B = \{w \mid w \text{ contains an even number of 0's}\}B={w∣w contains an even number of 0’s} .Give an NFA for A∘BA \circ BA∘B .

    A DFA for AAA ( q1,…,q4q_1, \dots, q_4q1​,…,q4​ ), then an ε\varepsilonε -transition from its accept state q4q_4q4​ to the start state q5q_5q5​ of a DFA for BBB . q4q_4q4​ is no longer accepting; q5q_5q5​ (even number of 0's) is the only accept state.

  34. [Exercises] Over Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} : A={w∣w starts with 00}A = \{w \mid w \text{ starts with } 00\}A={w∣w starts with 00} , B={w∣w starts with 11}B = \{w \mid w \text{ starts with } 11\}B={w∣w starts with 11} . Design a DFA and an NFA for A∪BA \cup BA∪B .

    DFA: read two symbols; 000000 and 111111 lead to accept states looping on 0, 1, while 010101 and 101010 lead to a non-accepting state looping on 0, 1. NFA: a new start state with ε\varepsilonε -transitions to an NFA for AAA and an NFA for BBB .

  35. [Exercises] Over Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} : A={w∣w ends with 00}A = \{w \mid w \text{ ends with } 00\}A={w∣w ends with 00} , B={w∣w contains at least two 1’s}B = \{w \mid w \text{ contains at least two 1's}\}B={w∣w contains at least two 1’s} . Design an NFA for A∘BA \circ BA∘B .

    A DFA for AAA , whose accept state gets an ε\varepsilonε -transition to the start of a DFA for BBB and stops being accepting. Top row: the string read ends with no 0, one 0, two 0's. Bottom row, right to left: zero, one, at least two 1's read.

  36. [Exercises] Over Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} : A={0110,110}A = \{0110, 110\}A={0110,110} . Design an NFA for A∗A^*A∗ .

    A new accepting start state, ε\varepsilonε to a state that reads 110110110 or 011001100110 along two branches, and ε\varepsilonε -transitions from both branch ends back to it.

  37. [Exercises] Over Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} : A={w∣w starts and ends with 1 and ∣w∣=3}A = \{w \mid w \text{ starts and ends with 1 and } |w| = 3\}A={w∣w starts and ends with 1 and ∣w∣=3} . Design an NFA for A∗A^*A∗ .

    A={101,111}A = \{101, 111\}A={101,111} : a new accepting start state, then a path reading 111 , 000 or 111 , 111 to an accept state with an ε\varepsilonε -transition back.

  38. [Exercises] Over Σ={a,b,c}\Sigma = \{a, b, c\}Σ={a,b,c} : A={w∣w starts with a}A = \{w \mid w \text{ starts with } a\}A={w∣w starts with a} , B={w∣w ends with b}B = \{w \mid w \text{ ends with } b\}B={w∣w ends with b} , C={w∣w contains cc}C = \{w \mid w \text{ contains } cc\}C={w∣w contains cc} . Design an NFA for (A∘B∪C)∗(A \circ B \cup C)^*(A∘B∪C)∗ .

    The star construction applied to the union construction of an NFA for A∘BA \circ BA∘B and an NFA for CCC . A∘BA \circ BA∘B = the strings that start with aaa and end with bbb .

  39. [Exercises] Over Σ={a,b}\Sigma = \{a, b\}Σ={a,b} : A={(ab)naa∣n≥0}A = \{(ab)^n aa \mid n \ge 0\}A={(ab)naa∣n≥0} , B={w∣∣w∣ is even}B = \{w \mid |w| \text{ is even}\}B={w∣∣w∣ is even} , C={w∣w starts and ends with b, ∣w∣≥3}C = \{w \mid w \text{ starts and ends with } b, \ |w| \ge 3\}C={w∣w starts and ends with b, ∣w∣≥3} . Design an NFA for A∘B∪CA \circ B \cup CA∘B∪C .

    A new start state with ε\varepsilonε -transitions to an NFA for A∘BA \circ BA∘B (left) and an NFA for CCC (right). Left: (ab)n(ab)^n(ab)n by the aaa / bbb cycle, then aaaaaa , then ε\varepsilonε to an accepting state with a 2-cycle on a,ba, ba,b (even length). Right: bbb , one symbol, any symbols, bbb .

  40. [Exercises] AAA is a regular language. Is its complement A‾\overline{A}A regular?

    Yes: in a DFA for AAA , make the accept states non-accepting and the non-accepting states accepting. This needs a DFA. Swapping in an NFA can fail: the NFA with q0undefined0q0q_0 \xrightarrow{0} q_0q0​0​q0​ , q0undefined0q1q_0 \xrightarrow{0} q_1q0​0​q1​ , accept state q1q_1q1​ recognizes {0}∗∖{ε}\{0\}^* \setminus \{\varepsilon\}{0}∗∖{ε} over {0}\{0\}{0} ; after swapping it accepts 000000 , which is not in the complement {ε}\{\varepsilon\}{ε} .

  41. [Exercises] AAA and BBB are regular languages. Why is A∩BA \cap BA∩B regular, using only closure under union and complement?

    A∩B=A‾∪B‾‾\boldsymbol{A \cap B = \overline{\overline{A} \cup \overline{B}}}A∩B=A∪B De Morgan's law. Another proof: the product DFA with accept states the pairs where both components are accepting.

  42. [Exercises] AAA and BBB are regular languages. Is the difference A∖BA \setminus BA∖B regular?

    Yes: A∖B=A∩B‾A \setminus B = A \cap \overline{B}A∖B=A∩B , and the regular languages are closed under complement and intersection.

  43. [Exercises] AAA is a regular language and ARA^RAR is the set of the reversals of its strings. Is ARA^RAR regular, and how do you build a machine for it?

    Yes: in a DFA for AAA , reverse every arrow; the old start state becomes the only accept state; a new start state gets ε\varepsilonε to each old accept state. The result is an NFA in general: after reversing, a state can have several outgoing arrows with the same symbol.Example: bbcb∈Abbcb \in Abbcb∈A gives bcbb∈ARbcbb \in A^Rbcbb∈AR .

  44. [Exercises] AAA is the language recognized by this NFA. Give an NFA for ARA^RAR , the reversals of the strings of AAA .

    Reverse every arrow, make the old accept state the start state and the old start state the accept state. A=a(bc)∗baa∪bbc∗b∪cc∪ccbc∗bA = a(bc)^*baa \cup bbc^*b \cup cc \cup ccbc^*bA=a(bc)∗baa∪bbc∗b∪cc∪ccbc∗b and AR=aab(cb)∗a∪bc∗bb∪cc∪bc∗bccA^R = aab(cb)^*a \cup bc^*bb \cup cc \cup bc^*bccAR=aab(cb)∗a∪bc∗bb∪cc∪bc∗bcc .