Ch.12: Regular Expressions and Finite-State Automata

Chapter 12 of the book "Discrete Mathematics with Applications" by Susanna S. Epp (4th edition) 12.1. Formal Languages and Regular Expressions 12.2. Finite-State Automata 12.3. Simplifying Finite-State Automata

119 flashcards · Mathematics · by lakesare

Part of Textbooks › Discrete Mathematics with Applications (Susanna Epp) · 12 courses

  1. [Formal Languages and Regular Expressions] What does the Church–Turing thesis assert?

    Anything that can be computed on any machine can be computed with a Turing machine. Turing machines are a simple abstract model of a machine, introduced by Alan Turing in the 1930s. The thesis is a conjecture (formulated by Alonzo Church), widely believed but not proved.Example: a quantum computer may compute some quantities much faster, but by the thesis it computes nothing that a Turing machine cannot.

  2. [Formal Languages and Regular Expressions] Who developed the theory of formal languages defined by grammars, and which two of its language classes are the most useful for computer science?

    Noam Chomsky (linguist, 1950s); the regular and the context-free languages. Regular languages are used for pattern matching in text and for lexical analysis in compilers; context-free languages (written in Backus-Naur notation) describe the syntax of high-level programming languages.

  3. [Formal Languages and Regular Expressions] Each regular expression and each context-free grammar is equivalent to a type of automaton. Which types?

    Regular expression equivalent to a finite-state automaton Context-free grammar equivalent to a pushdown automaton

  4. [Formal Languages and Regular Expressions] What are the three parts of a compiler, in the order they process a program?

    Lexical scanner recognizes the individual words of the program in the stream of characters Syntactic analyzer analyzes the syntax (grammar) of the sentences Code generator translates the sentences into machine code

  5. [Formal Languages and Regular Expressions] What are an alphabet Σ\SigmaΣ , a string over Σ\SigmaΣ , and the length of a string?

    Alphabet Σ\SigmaΣ a finite set of characters Example: Σ={a,b}\Sigma = \{a, b\}Σ={a,b} . String over Σ\SigmaΣ a finite sequence of elements (characters) of Σ\SigmaΣ , or the null string ε\varepsilonε Example: abbaabbaabba is a string over {a,b}\{a, b\}{a,b} . Length the number of characters of the string; the null string ε\varepsilonε has length 0 Example: abbaabbaabba has length 4.

  6. [Formal Languages and Regular Expressions] What is a formal language over an alphabet Σ\SigmaΣ ?

    Any set of strings over Σ\SigmaΣ . The empty set ∅\emptyset∅ is also a formal language; this is convenient in technical situations.Example: over Σ={a,b}\Sigma = \{a, b\}Σ={a,b} , the set of strings that begin with aaa and have length at most 3 is {a,aa,ab,aaa,aab,aba,abb}\{a, aa, ab, aaa, aab, aba, abb\}{a,aa,ab,aaa,aab,aba,abb} .

  7. [Formal Languages and Regular Expressions] What is a palindrome? Give some palindromes over {a,b}\{a, b\}{a,b} .

    A string that is the same when the order of its characters is reversed. Example: ε, a, b, aa, bb, aaa, bab, abba, babaabab\varepsilon, \ a, \ b, \ aa, \ bb, \ aaa, \ bab, \ abba, \ babaababε, a, b, aa, bb, aaa, bab, abba, babaabab (and infinitely many more).

  8. [Formal Languages and Regular Expressions] Σ\SigmaΣ is an alphabet and n≥0n \ge 0n≥0 . What are Σn\Sigma^nΣn , Σ+\Sigma^+Σ+ and Σ∗\Sigma^*Σ∗ ?

    Σn\Sigma^nΣn the set of all strings over Σ\SigmaΣ of length nnn Example: for Σ={a,b}\Sigma = \{a, b\}Σ={a,b} : Σ2={aa,ab,ba,bb}\Sigma^2 = \{aa, ab, ba, bb\}Σ2={aa,ab,ba,bb} . Σ+\Sigma^+Σ+ the set of all strings over Σ\SigmaΣ of length at least 1 Example: for Σ={a,b}\Sigma = \{a, b\}Σ={a,b} : a,b,aa,ab,ba,bb,aaa,…a, b, aa, ab, ba, bb, aaa, \dotsa,b,aa,ab,ba,bb,aaa,… Σ∗\Sigma^*Σ∗ the set of all strings over Σ\SigmaΣ Example: for Σ={a,b}\Sigma = \{a, b\}Σ={a,b} : ε,a,b,aa,ab,ba,bb,aaa,…\varepsilon…

  9. [Formal Languages and Regular Expressions] For an alphabet Σ\SigmaΣ , the set Σ∗\Sigma^*Σ∗ of all strings is called the Kleene closure of Σ\SigmaΣ , and Σ+\Sigma^+Σ+ is called the positive closure of Σ\SigmaΣ .

    Named after Stephen C. Kleene (pronounced CLAY-knee). Σ+\Sigma^+Σ+ is Σ∗\Sigma^*Σ∗ without the null string ε\varepsilonε . Example: for Σ={a}\Sigma = \{a\}Σ={a} : Σ∗={ε,a,aa,… }\Sigma^* = \{\varepsilon, a, aa, \dots\}Σ∗={ε,a,aa,…} and Σ+={a,aa,… }\Sigma^+ = \{a, aa, \dots\}Σ+={a,aa,…} .

  10. [Formal Languages and Regular Expressions] Σ={a,b}\Sigma = \{a, b\}Σ={a,b} . What is Σ0\Sigma^0Σ0 , and what is Σ0∪Σ1\Sigma^0 \cup \Sigma^1Σ0∪Σ1 in words?

    Σ0={ε}\boldsymbol{\Sigma^0 = \{\varepsilon\}}Σ0={ε} ; Σ0∪Σ1\Sigma^0 \cup \Sigma^1Σ0∪Σ1 is the set of strings over Σ\SigmaΣ of length at most 1. Σ0\Sigma^0Σ0 is not empty: it contains the one string of length 0.Example: Σ0∪Σ1={ε,a,b}\Sigma^0 \cup \Sigma^1 = \{\varepsilon, a, b\}Σ0∪Σ1={ε,a,b} .

  11. [Formal Languages and Regular Expressions] How can you list the elements of the infinite set Σ+\Sigma^+Σ+ systematically, and what changes for Σ∗\Sigma^*Σ∗ ?

    List all strings of length 1, then all of length 2, and so on; for Σ∗\Sigma^*Σ∗ , put ε\varepsilonε first. Example: for Σ={a,b}\Sigma = \{a, b\}Σ={a,b} : a,b,aa,ab,ba,bb,aaa,aab,aba,abb,baa,bab,bba,bbb,aaaa,…a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaa, \dotsa,b,aa,ab,ba,bb,aaa,aab,aba,abb,baa,bab,bba,bbb,aaaa,…

  12. [Formal Languages and Regular Expressions] What are infix, prefix and postfix notation for a binary operator?

    Infix the operator is written between the two quantities it acts on Example: a+ba + ba+b Prefix (Polish notation) the operator is written before the two quantities Example: + ab+\,ab+ab Postfix (reverse Polish notation) the operator is written after the two quantities Example: ab +ab\,+ab+ Prefix and postfix notation were introduced in 1920 by the Polish mathematician Jan Łukasiewicz.

  13. [Formal Languages and Regular Expressions] What is the great advantage of prefix and postfix notation over infix notation?

    They need no parentheses. Example: (a+b)⋅c(a + b) \cdot c(a+b)⋅c in infix is ab+c ⋅ab + c\,\cdotab+c⋅ in postfix.

  14. [Formal Languages and Regular Expressions] Evaluate the postfix expression 8 4 + 6 /8 \ 4 \ + \ 6 \ /8 4 + 6 / .

    2\boldsymbol{2}2 From left to right: add 8 and 4 to obtain 12, then divide 12 by 6.

  15. [Formal Languages and Regular Expressions] Convert the postfix expression ab⋅cd⋅+ab \cdot cd \cdot +ab⋅cd⋅+ to infix notation.

    a⋅b+c⋅d\boldsymbol{a \cdot b + c \cdot d}a⋅b+c⋅d ab ⋅ab\,\cdotab⋅ is a⋅ba \cdot ba⋅b , cd ⋅cd\,\cdotcd⋅ is c⋅dc \cdot dc⋅d , and the final +++ adds the two.

  16. [Formal Languages and Regular Expressions] Σ\SigmaΣ is an alphabet, x,yx, yx,y are strings and L,L′L, L'L,L′ are languages over Σ\SigmaΣ . Define the concatenation xyxyxy , and the languages LL′LL'LL′ , L∪L′L \cup L'L∪L′ and L∗L^*L∗ .

    Concatenation xyxyxy of strings all characters of xxx followed by all characters of yyy Example: x=abx = abx=ab , y=bay = bay=ba : xy=abbaxy = abbaxy=abba . Concatenation of languages LL′={xy∣x∈L and y∈L′}LL' = \{xy \mid x \in L \text{ and } y \in L'\}LL′={xy∣x∈L and y∈L′} Example: {a,b}{c}={ac,bc}\{a, b\}\{c\} = \{ac, bc\}{a,b}{c}={ac,bc} . Union L∪L′={x∣x∈L or x∈L′}L \cup L' = \{x \mid x \in L \text{ or } x \in L'\}L∪L′={x∣x∈L or x∈L′} Example: {a,b}∪{c}={a,b,c}\{a, b\} \c…

  17. [Formal Languages and Regular Expressions] LLL is any language. Why is the null string ε\varepsilonε always in L∗L^*L∗ ?

    ε\varepsilonε is the concatenation of zero strings in LLL . L∗L^*L∗ is the set of concatenations of any finite number of strings in LLL , and 0 is such a number.Example: ∅∗={ε}\emptyset^* = \{\varepsilon\}∅∗={ε} .

  18. [Formal Languages and Regular Expressions] L1L_1L1​ is the set of strings consisting of an even number of aaa 's ( ε,aa,aaaa,…\varepsilon, aa, aaaa, \dotsε,aa,aaaa,… ) and L2={b,bb,bbb}L_2 = \{b, bb, bbb\}L2​={b,bb,bbb} . Describe L1L2L_1L_2L1​L2​ .

    An even number of aaa 's followed by bbb , bbbbbb or bbbbbbbbb . ε∈L1\varepsilon \in L_1ε∈L1​ since 0 is even, so b∈L1L2b \in L_1L_2b∈L1​L2​ .Example: aabb∈L1L2aabb \in L_1L_2aabb∈L1​L2​ , but abb∉L1L2abb \notin L_1L_2abb∈/L1​L2​ .

  19. [Formal Languages and Regular Expressions] L1L_1L1​ is the set of strings consisting of an even number of aaa 's ( ε,aa,aaaa,…\varepsilon, aa, aaaa, \dotsε,aa,aaaa,… ) and L2={b,bb,bbb}L_2 = \{b, bb, bbb\}L2​={b,bb,bbb} . Describe (L1∪L2)∗(L_1 \cup L_2)^*(L1​∪L2​)∗ .

    The strings of aaa 's and bbb 's in which every aaa is in a block of an even number of aaa 's. Any number of bbb 's can be built from bbb , and the aaa 's come in pieces aa,aaaa,…aa, aaaa, \dotsaa,aaaa,… Example: aabaaaab∈(L1∪L2)∗aabaaaab \in (L_1 \cup L_2)^*aabaaaab∈(L1​∪L2​)∗ , but aba∉(L1∪L2)∗aba \notin (L_1 \cup L_2)^*aba∈/(L1​∪L2​)∗ .

  20. [Formal Languages and Regular Expressions] Give the recursive definition of a regular expression over an alphabet Σ\SigmaΣ .

    Base ∅\emptyset∅ , ε\varepsilonε , and each individual symbol of Σ\SigmaΣ are regular expressions over Σ\SigmaΣ . Recursion If rrr and sss are regular expressions over Σ\SigmaΣ , so are (rs)(rs)(rs) , (r∣s)(r \mid s)(r∣s) and (r∗)(r^*)(r∗) . rsrsrs is the concatenation of rrr and sss ; r∣sr \mid sr∣s is either of rrr and sss ; r∗r^*r∗ (the Kleene closure of rrr ) is rrr concatenated with itself any finite number of times, including zero. Restriction Nothing else is a regular expression over Σ\S…

  21. [Formal Languages and Regular Expressions] The alphabet of a regular expression contains a symbol such as ((( , ∣|∣ or ∗*∗ . How is the ambiguity avoided?

    An escape character, usually a backslash, is written before the symbol. Example: a left parenthesis is written as \(\backslash(\( , and the backslash itself as \\\backslash\backslash\\ .

  22. [Formal Languages and Regular Expressions] What is the order of precedence of the operations in a regular expression?

    ∗^*∗ highest, then concatenation, then ∣|∣ lowest. The outer pair of parentheses is also dropped.Example: (a((bc)∗))=a(bc)∗(a((bc)^*)) = a(bc)^*(a((bc)∗))=a(bc)∗ and (a∣(bc))=a∣bc(a \mid (bc)) = a \mid bc(a∣(bc))=a∣bc .

  23. [Formal Languages and Regular Expressions] Add parentheses to ab∗∣b∗aab^* \mid b^*aab∗∣b∗a to make the order of precedence explicit.

    ((a(b∗))∣((b∗)a))\boldsymbol{((a(b^*)) \mid ((b^*)a))}((a(b∗))∣((b∗)a)) ∗^*∗ binds first, then concatenation, then ∣|∣ .

  24. [Formal Languages and Regular Expressions] Use the order of precedence to remove parentheses from ((a∣((b∗)c))(a∗))((a \mid ((b^*)c))(a^*))((a∣((b∗)c))(a∗)) .

    (a∣b∗c)a∗\boldsymbol{(a \mid b^*c)a^*}(a∣b∗c)a∗ The parentheses around a∣b∗ca \mid b^*ca∣b∗c must stay: concatenation has higher precedence than ∣|∣ .

  25. [Formal Languages and Regular Expressions] How is the language L(r)L(r)L(r) defined by a regular expression rrr over Σ\SigmaΣ defined in the BASE case?

    L(∅)=∅\boldsymbol{L(\emptyset) = \emptyset}L(∅)=∅ , L(ε)={ε}\;\boldsymbol{L(\varepsilon) = \{\varepsilon\}}L(ε)={ε} , L(a)={a}\;\boldsymbol{L(a) = \{a\}}L(a)={a} for every a∈Σa \in \Sigmaa∈Σ L(∅)L(\emptyset)L(∅) contains no string; L(ε)L(\varepsilon)L(ε) contains one string, the null string.

  26. [Formal Languages and Regular Expressions] rrr and r′r'r′ are regular expressions. How is the language they define extended to L(rr′)L(rr')L(rr′) , L(r∣r′)L(r \mid r')L(r∣r′) and L(r∗)L(r^*)L(r∗) ?

    L(rr′)=L(r)L(r′)\boldsymbol{L(rr') = L(r)L(r')}L(rr′)=L(r)L(r′) , L(r∣r′)=L(r)∪L(r′)\;\boldsymbol{L(r \mid r') = L(r) \cup L(r')}L(r∣r′)=L(r)∪L(r′) , L(r∗)=(L(r))∗\;\boldsymbol{L(r^*) = (L(r))^*}L(r∗)=(L(r))∗ Concatenation of languages, union, and Kleene closure of a language.Example: L(a∣bc)={a}∪{bc}={a,bc}L(a \mid bc) = \{a\} \cup \{bc\} = \{a, bc\}L(a∣bc)={a}∪{bc}={a,bc} .

  27. [Formal Languages and Regular Expressions] Is every finite language defined by some regular expression?

    Yes: join its strings with ∣|∣ . Example: {cat,dog,bird}\{cat, dog, bird\}{cat,dog,bird} is defined by cat∣dog∣birdcat \mid dog \mid birdcat∣dog∣bird .

  28. [Formal Languages and Regular Expressions] Σ={a,b}\Sigma = \{a, b\}Σ={a,b} . Use the definition of LLL to find L((a∣b)∗)L((a \mid b)^*)L((a∣b)∗) .

    Σ∗\boldsymbol{\Sigma^*}Σ∗ , the set of all strings of aaa 's and bbb 's. L((a∣b)∗)=(L(a∣b))∗=(L(a)∪L(b))∗=({a}∪{b})∗={a,b}∗L((a \mid b)^*) = (L(a \mid b))^* = (L(a) \cup L(b))^* = (\{a\} \cup \{b\})^* = \{a, b\}^*L((a∣b)∗)=(L(a∣b))∗=(L(a)∪L(b))∗=({a}∪{b})∗={a,b}∗ .

  29. [Formal Languages and Regular Expressions] rrr , sss , ttt are regular expressions. Why may one write rstrstrst and r∣s∣tr \mid s \mid tr∣s∣t without parentheses?

    Concatenation of strings and union of sets are both associative, so both ways of bracketing define the same language. Example: L((r∣s)∣t)=(L(r)∪L(s))∪L(t)=L(r)∪(L(s)∪L(t))=L(r∣(s∣t))L((r \mid s) \mid t) = (L(r) \cup L(s)) \cup L(t) = L(r) \cup (L(s) \cup L(t)) = L(r \mid (s \mid t))L((r∣s)∣t)=(L(r)∪L(s))∪L(t)=L(r)∪(L(s)∪L(t))=L(r∣(s∣t)) .

  30. [Formal Languages and Regular Expressions] Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} . Describe in words the language defined by 0∗1∗∣1∗0∗0^*1^* \mid 1^*0^*0∗1∗∣1∗0∗ .

    A string of 0's followed by a string of 1's, or a string of 1's followed by a string of 0's. Either part may be empty, so ε\varepsilonε is in the language.Example: 001100110011 and 111011101110 are in it, 010010010 is not.

  31. [Formal Languages and Regular Expressions] Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} . Describe in words the language defined by 0(0∣1)∗0(0 \mid 1)^*0(0∣1)∗ .

    All strings of 0's and 1's that start with 0. The first 0 may be followed by any finite number (including zero) of 0's and 1's in any order.

  32. [Formal Languages and Regular Expressions] Σ={a,b}\Sigma = \{a, b\}Σ={a,b} . Which of aaa , bbb , aaaaaaaaaaaa , abbaabbaabba , ababababababababab belong to the language defined by a∗∣(ab)∗a^* \mid (ab)^*a∗∣(ab)∗ ?

    aaa , aaaaaaaaaaaa and ababababababababab . bbb is neither a string of aaa 's nor a string of repeated ababab 's; in abbaabbaabba two bbb 's are not separated by an aaa .

  33. [Formal Languages and Regular Expressions] Σ={a,b}\Sigma = \{a, b\}Σ={a,b} . Describe the language defined by a∗b(a∣b)∗a^*b(a \mid b)^*a∗b(a∣b)∗ and give five of its strings.

    All strings of aaa 's and bbb 's that contain at least one bbb . Example: b, ab, abbb, abaaa, ababbab, \ ab, \ abbb, \ abaaa, \ ababbab, ab, abbb, abaaa, ababba .

  34. [Formal Languages and Regular Expressions] Give a regular expression over {0,1}\{0, 1\}{0,1} for the strings of even length in which 0's and 1's alternate.

    (10)∗∣(01)∗\boldsymbol{(10)^* \mid (01)^*}(10)∗∣(01)∗ A string that starts with 1 repeats 101010 ; one that starts with 0 repeats 010101 . The null string also qualifies.

  35. [Formal Languages and Regular Expressions] What does it mean that a string of 0's and 1's has even parity? Give a regular expression for these strings.

    It has an even number of 1's. Regular expression: (0∣10∗1)∗\boldsymbol{(0 \mid 10^*1)^*}(0∣10∗1)∗ . ε\varepsilonε , 000 and 10∗110^*110∗1 have even parity, and a concatenation of strings with even parity has even parity.Example: 0110=0⋅11⋅00110 = 0 \cdot 11 \cdot 00110=0⋅11⋅0 and 10010=1001⋅010010 = 1001 \cdot 010010=1001⋅0 have even parity, with 11,1001∈L(10∗1)11, 1001 \in L(10^*1)11,1001∈L(10∗1) .

  36. [Formal Languages and Regular Expressions] Give a regular expression over {0,1}\{0, 1\}{0,1} for the strings that do not contain two consecutive 1's.

    (0∣10)∗(ε∣1)\boldsymbol{(0 \mid 10)^*(\varepsilon \mid 1)}(0∣10)∗(ε∣1) Every 1 must be followed immediately by a 0, except a 1 at the end of the string.Example: 01001=0⋅10⋅0⋅101001 = 0 \cdot 10 \cdot 0 \cdot 101001=0⋅10⋅0⋅1 .

  37. [Formal Languages and Regular Expressions] Do (a∣ε)∗(a \mid \varepsilon)^*(a∣ε)∗ and a∗a^*a∗ define the same language? Do (a∗∣b∗)∗(a^* \mid b^*)^*(a∗∣b∗)∗ and (a∣b)∗(a \mid b)^*(a∣b)∗ ?

    Yes and yes. xε=εx=xx\varepsilon = \varepsilon x = xxε=εx=x for every string xxx , so (a∣ε)∗(a \mid \varepsilon)^*(a∣ε)∗ gives the strings of zero or more aaa 's. Both (a∗∣b∗)∗(a^* \mid b^*)^*(a∗∣b∗)∗ and (a∣b)∗(a \mid b)^*(a∣b)∗ give all strings of aaa 's and bbb 's.

  38. [Formal Languages and Regular Expressions] Do 0∗∣1∗0^* \mid 1^*0∗∣1∗ and (01)∗(01)^*(01)∗ define the same language?

    No: 010101010101 is in L((01)∗)L((01)^*)L((01)∗) but not in L(0∗∣1∗)L(0^* \mid 1^*)L(0∗∣1∗) . 0∗∣1∗0^* \mid 1^*0∗∣1∗ gives only strings of one repeated symbol.

  39. [Formal Languages and Regular Expressions] The UNIX utility grep is short for "globally search for regular expression and print".

    Regular expressions are also used in text editors (QED, vi, sed, Emacs) and in the lexical scanner of a compiler.

  40. [Formal Languages and Regular Expressions] What does the character class [A-C][A\text{-}C][A-C] stand for, and what does [A-C x-z][A\text{-}C\,x\text{-}z][A-Cx-z] stand for?

    (A∣B∣C)\boldsymbol{(A \mid B \mid C)}(A∣B∣C) and (A∣B∣C∣x∣y∣z)\boldsymbol{(A \mid B \mid C \mid x \mid y \mid z)}(A∣B∣C∣x∣y∣z) A character class is a single character from the given range(s), in the standard order of the alphabet.Example: [0-9][0\text{-}9][0-9] stands for (0∣1∣2∣⋯∣9)(0 \mid 1 \mid 2 \mid \dots \mid 9)(0∣1∣2∣⋯∣9) , and [ABC][ABC][ABC] for (A∣B∣C)(A \mid B \mid C)(A∣B∣C) .

  41. [Formal Languages and Regular Expressions] Describe the language defined by [A-Z a-z]([A-Z a-z]∣[0-9])∗[A\text{-}Z\,a\text{-}z]([A\text{-}Z\,a\text{-}z] \mid [0\text{-}9])^*[A-Za-z]([A-Za-z]∣[0-9])∗ .

    All strings that start with a letter, followed by any sequence of letters and digits. This is the set of allowed identifiers in many programming languages.Example: z23z23z23 , jsmith109jsmith109jsmith109 , Draft2revDraft2revDraft2rev .

  42. [Formal Languages and Regular Expressions] In regular-expression shorthand, what does a single dot stand for? What does A.CA.CA.C stand for when Σ={A,B,C}\Sigma = \{A, B, C\}Σ={A,B,C} ?

    An arbitrary character; so A.CA.CA.C stands for (AAC∣ABC∣ACC)\boldsymbol{(AAC \mid ABC \mid ACC)}(AAC∣ABC∣ACC) .

  43. [Formal Languages and Regular Expressions] What does ^\text{\textasciicircum}^ mean at the beginning of a character class, as in [^D-Z][0-9][0-9]∗[\text{\textasciicircum}D\text{-}Z][0\text{-}9][0\text{-}9]^*[^D-Z][0-9][0-9]∗ ?

    A character of the same type as those in the class, except one of the characters listed after the ^\text{\textasciicircum}^ . So the expression gives a letter other than D,…,ZD, \dots, ZD,…,Z , followed by one or more digits.Example: B3097B3097B3097 , C0046C0046C0046 .

  44. [Formal Languages and Regular Expressions] rrr is a regular expression and m≤nm \le nm≤n are positive integers. What do r+r+r+ , r?r?r? , r{n}r\{n\}r{n} and r{m,n}r\{m, n\}r{m,n} denote?

    r+r+r+ rrr concatenated with itself any positive finite number of times: r+=rr∗r+ = rr^*r+=rr∗ Example: [A-Z]+[A\text{-}Z]+[A-Z]+ gives any nonempty string of capital letters. r?r?r? zero occurrences or exactly one occurrence of rrr : r?=(ε∣r)r? = (\varepsilon \mid r)r?=(ε∣r) Example: ab?ab?ab? gives aaa and ababab . r{n}r\{n\}r{n} rrr concatenated with itself exactly nnn times Example: [0-9]{3}-[0-9]{4}[0\text{-}9]\{3\}\text{-}[0\text{-}9]\{4\}[0-9]{3}-[0-9]{4} gives US local telephone numbers…

  45. [Formal Languages and Regular Expressions] US dates like 2/5/2050, 2-5-2050, 02/05/2050 or 02-05-2050 are to be checked. Give a regular expression for them.

    [0-9]{1,2}[-/][0-9]{1,2}[-/][0-9]{4}\boldsymbol{[0\text{-}9]\{1, 2\}[\text{-}/][0\text{-}9]\{1, 2\}[\text{-}/][0\text{-}9]\{4\}}[0-9]{1,2}[-/][0-9]{1,2}[-/][0-9]{4} One or two digits, a hyphen or a slash, one or two digits, a hyphen or a slash, four digits.

  46. [Formal Languages and Regular Expressions] Dates like 02/05/2050 are checked with [0-9]{1,2}[-/][0-9]{1,2}[-/][0-9]{4}[0\text{-}9]\{1, 2\}[\text{-}/][0\text{-}9]\{1, 2\}[\text{-}/][0\text{-}9]\{4\}[0-9]{1,2}[-/][0-9]{1,2}[-/][0-9]{4} .Does every string in this language represent a valid date?

    No. Example: 09/54/197809/54/197809/54/1978 (September has no 54th day) and 38/12/218438/12/218438/12/2184 (there is no 38th month) are in the language. The expression is still useful for detecting some kinds of input mistakes.

  47. [Finite-State Automata] What is the difference between a combinational circuit and a sequential circuit?

    Combinational circuit its output is completely determined by its input (a Boolean function); it has no memory Sequential circuit its output depends on the input and on the state the circuit is in when the input is received Example: a computer memory circuit. A finite-state automaton is an idealized machine with the essential idea of a sequential circuit.

  48. [Finite-State Automata] A vending machine sells juice for 1 dollar, accepts quarters (25 cents) and half-dollars (50 cents), and gives no change. Its transition diagram: In which state is the machine after: quarter, half-dollar, half-dollar?

    "1 dollar or more deposited", and a bottle of juice is released. 0→25→75→0 \to 25 \to 75 \to0→25→75→ "1 dollar or more" (the buyer pays 1.25 dollars). The next coin starts over: a quarter then gives "25 cents deposited".

  49. [Finite-State Automata] In the transition diagram of a finite-state automaton, what do the following mean: a circle, a double circle, the unlabeled arrow, and an arrow from state sss to state ttt labeled mmm ?

    Circle a state Double circle an accepting state Unlabeled arrow points to the initial state Arrow from sss to ttt labeled mmm N(s,m)=tN(s, m) = tN(s,m)=t : in state sss , input mmm makes the automaton go to state ttt

  50. [Finite-State Automata] A computer has nnn locations, each storing a single bit. How many states can it be in, and why does that make it a finite-state automaton?

    2n\boldsymbol{2^n}2n states: an enormous number, but finite. So, as for a vending machine, the next state is determined by the current state and the input.

  51. [Finite-State Automata] What are the five objects that make up a finite-state automaton AAA ?

    Input alphabet III a finite set of input symbols States SSS a finite set of states Initial state s0s_0s0​ a designated state in SSS Accepting states a designated set of states Next-state function N:S×I→SN: S \times I \to SN:S×I→S N(s,m)N(s, m)N(s,m) is the state to which AAA goes if mmm is input when AAA is in state sss Example: the vending machine has I={I = \{I={ quarter, half-dollar }\}} , five states, initial state "0 cents deposited", and one accepting state "1 dollar or more deposited".

  52. [Finite-State Automata] What does the next-state table of an automaton show, and how does the annotated next-state table mark the initial and the accepting states?

    The values N(s,i)N(s, i)N(s,i) of the next-state function for all states sss and input symbols iii . Initial state: an arrow; accepting states: double circles ⊚\circledcirc⊚ . Row sss , column iii holds N(s,i)N(s, i)N(s,i) . The table and the transition diagram give exactly the same information.

  53. [Finite-State Automata] Write the annotated next-state table of this automaton AAA , and give its initial and accepting states.

    01→s0s1s0s1s1s2⊚s2s1s0\boldsymbol{\begin{array}{cc|cc} & & 0 & 1 \\ \hline \to & s_0 & s_1 & s_0 \\ & s_1 & s_1 & s_2 \\ \circledcirc & s_2 & s_1 & s_0 \end{array}}→⊚​s0​s1​s2​​0s1​s1​s1​​1s0​s2​s0​​​ States s0,s1,s2s_0, s_1, s_2s0​,s1​,s2​ ; input symbols 0, 1; initial state s0s_0s0​ (the unlabeled arrow); only accepting state s2s_2s2​ (the double circle).

  54. [Finite-State Automata] An automaton AAA has this annotated next-state table. Draw its transition diagram. abc→UZYY⊚VVVVYZVY⊚ZZZZ\begin{array}{cc|ccc} & & a & b & c \\ \hline \to & U & Z & Y & Y \\ \circledcirc & V & V & V & V \\ & Y & Z & V & Y \\ \circledcirc & Z & Z & Z & Z \end{array}→⊚⊚​UVYZ​aZVZZ​bYVVZ​cYVYZ​​

    Initial state UUU , accepting states VVV and ZZZ : One arrow may carry several input symbols: e.g. N(U,b)=N(U,c)=YN(U, b) = N(U, c) = YN(U,b)=N(U,c)=Y gives one arrow labeled b,cb, cb,c .

  55. [Finite-State Automata] AAA is a finite-state automaton with set of input symbols III , and w∈I∗w \in I^*w∈I∗ . When is www accepted by AAA ?

    When AAA goes to an accepting state as the symbols of www are input from left to right, starting in the initial state. So AAA separates I∗I^*I∗ into two subsets: the accepted strings and the others.

  56. [Finite-State Automata] What is the language accepted by a finite-state automaton AAA , written L(A)L(A)L(A) ?

    The set of all strings accepted by AAA . A string is accepted when its symbols, input from left to right starting in the initial state, send AAA to an accepting state.

  57. [Finite-State Automata] To what states do the strings 010101 , 001100110011 , 010110001011000101100 , 101011010110101 send this automaton, starting from s0s_0s0​ ? Which are accepted?

    s2s_2s2​ , s0s_0s0​ , s1s_1s1​ , s2s_2s2​ ; so 010101 and 101011010110101 are accepted. 001100110011 : s0undefined0s1undefined0s1undefined1s2undefined1s0s_0 \xrightarrow{0} s_1 \xrightarrow{0} s_1 \xrightarrow{1} s_2 \xrightarrow{1} s_0s0​0​s1​0​s1​1​s2​1​s0​ .

  58. [Finite-State Automata] What language does this automaton accept? Give a regular expression for it.

    The strings of 0's and 1's that end in 010101 : (0∣1)∗01\boldsymbol{(0 \mid 1)^*01}(0∣1)∗01 . From every state, input 010101 leads to s1s_1s1​ and then to s2s_2s2​ . Conversely, the only arrow into the accepting state s2s_2s2​ comes from s1s_1s1​ with label 1, and all arrows into s1s_1s1​ are labeled 0.

  59. [Finite-State Automata] How do finite-state automata with several accepting states help a compiler's lexical scanner?

    Each accepting state gets its own output, so the automaton classifies input strings into categories, one per accepting state. Example: grouping the characters of a program into identifiers, keywords, and so on.

  60. [Finite-State Automata] AAA has states SSS , input symbols III and next-state function NNN . What is the eventual-state function N∗:S×I∗→SN^*: S \times I^* \to SN∗:S×I∗→S ?

    N∗(s,w)N^*(s, w)N∗(s,w) = the state to which AAA goes if the symbols of www are input in sequence, starting when AAA is in state sss . The start state sss need not be the initial state.Example: N∗(s,ε)=sN^*(s, \varepsilon) = sN∗(s,ε)=s and N∗(s,m)=N(s,m)N^*(s, m) = N(s, m)N∗(s,m)=N(s,m) for a single symbol mmm .

  61. [Finite-State Automata] For this automaton, find N∗(s1,10110)N^*(s_1, 10110)N∗(s1​,10110) .

    N∗(s1,10110)=s1\boldsymbol{N^*(s_1, 10110) = s_1}N∗(s1​,10110)=s1​ s1undefined1s2undefined0s1undefined1s2undefined1s0undefined0s1s_1 \xrightarrow{1} s_2 \xrightarrow{0} s_1 \xrightarrow{1} s_2 \xrightarrow{1} s_0 \xrightarrow{0} s_1s1​1​s2​0​s1​1​s2​1​s0​0​s1​

  62. [Finite-State Automata] AAA has initial state s0s_0s0​ , input symbols III and eventual-state function N∗N^*N∗ . Express " www is accepted by AAA " and L(A)L(A)L(A) using N∗N^*N∗ .

    www is accepted ⇔\Leftrightarrow⇔ N∗(s0,w)N^*(s_0, w)N∗(s0​,w) is an accepting state; L(A)={w∈I∗∣N∗(s0,w) is accepting}\;\boldsymbol{L(A) = \{w \in I^* \mid N^*(s_0, w) \text{ is accepting}\}}L(A)={w∈I∗∣N∗(s0​,w) is accepting}

  63. [Finite-State Automata] Design a finite-state automaton that accepts the strings of 0's and 1's in which the number of 1's is divisible by 3.

    Three states s0,s1,s2s_0, s_1, s_2s0​,s1​,s2​ : sis_isi​ means "the number of 1's input so far has remainder iii modulo 3"; s0s_0s0​ is initial and accepting. Input 0 leaves the state unchanged; input 1 goes s0→s1→s2→s0s_0 \to s_1 \to s_2 \to s_0s0​→s1​→s2​→s0​ .Regular expression: 0∗∣(0∗10∗10∗10∗)∗0^* \mid (0^*10^*10^*10^*)^*0∗∣(0∗10∗10∗10∗)∗ .

  64. [Finite-State Automata] An automaton accepts the strings of 0's and 1's whose number of 1's is divisible by 3. State sks_ksk​ is reached after kkk 1's, for k=0,1,2k = 0, 1, 2k=0,1,2 .Why must s0,s1,s2s_0, s_1, s_2s0​,s1​,s2​ be different, and why are no more states needed?

    Different: from s0s_0s0​ , s1s_1s1​ , s2s_2s2​ , the numbers of further 1's needed are 3, 2, 1. Enough: after 3k3k3k , 3k+13k+13k+1 , 3k+23k+23k+2 ones the situation is that of s0s_0s0​ , s1s_1s1​ , s2s_2s2​ . Every nonnegative integer has one of the forms 3k3k3k , 3k+13k + 13k+1 , 3k+23k + 23k+2 . Example: after four 1's ( 4=3+14 = 3 + 14=3+1 ), two more 1's are needed, as in s1s_1s1​ .

  65. [Finite-State Automata] Design a finite-state automaton that accepts the strings of 0's and 1's that contain exactly one 1. Give a regular expression too.

    s0s_0s0​ (no 1 yet), s1s_1s1​ (exactly one 1, accepting), s2s_2s2​ (two or more 1's, never left). Regular expression: 0∗10∗\boldsymbol{0^*10^*}0∗10∗ .

  66. [Finite-State Automata] An automaton for "exactly one 1" has initial state s0s_0s0​ (0's only so far) and accepting state s1s_1s1​ (exactly one 1 so far).In s1s_1s1​ , a second 1 is input. Why can't the automaton go back to s0s_0s0​ ?

    From s0s_0s0​ an input 1 leads to s1s_1s1​ , so a string with three 1's would be accepted. A third state s2s_2s2​ is needed, from which no input leads back to s1s_1s1​ : every input leaves the automaton in s2s_2s2​ .

  67. [Finite-State Automata] Two algorithms simulate this automaton (it accepts the strings of 0's and 1's ending in 011). How do they work?

    Mimic the transition diagram nested if-then-else: for each state and each symbol, set the new state (e.g. if state = 2 and symbol = 1 then state := 3) Next-state function as an array store NNN as a two-dimensional array and repeat state := NNN (state, symbol) N(0,0)=1N(0,0) = 1N(0,0)=1 , N(0,1)=0N(0,1) = 0N(0,1)=0 , N(1,0)=1N(1,0) = 1N(1,0)=1 , N(1,1)=2N(1,1) = 2N(1,1)=2 , N(2,0)=1N(2,0) = 1N(2,0)=1 , N(2,1)=3N(2,1) = 3N(2,1)=3 , N(3,0)=1N(3,0) = 1N(3,0)=1 , N(3,1)=0N(3,1) = 0N(3,1)=0 Both star…

  68. [Finite-State Automata] Kleene's Theorem, Part 1. Given any language that is accepted by a finite-state automaton, … ?

    There is a regular expression that defines the same language.

  69. [Finite-State Automata] Kleene's Theorem, Part 2. Given any language defined by a regular expression, … ?

    There is a finite-state automaton that accepts the same language.

  70. [Finite-State Automata] AAA has states s1,…,sns_1, \dots, s_ns1​,…,sn​ ( s1s_1s1​ initial) and input alphabet III . In the proof of Kleene's theorem (automaton ⇒\Rightarrow⇒ regular expression), what is the set Li,jkL^k_{i,j}Li,jk​ ?

    The strings x∈I∗x \in I^*x∈I∗ whose symbols send AAA from sis_isi​ to sjs_jsj​ without passing through an intermediate state shs_hsh​ with h>kh > kh>k . iii or jjj themselves may be greater than kkk ; only the states visited in between are restricted.Example: L1,jnL^n_{1,j}L1,jn​ is the set of all strings that send AAA from s1s_1s1​ to sjs_jsj​ , so L(A)L(A)L(A) is the union of the L1,jnL^n_{1,j}L1,jn​ over the accepting states sjs_jsj​ .

  71. [Finite-State Automata] Li,jkL^k_{i,j}Li,jk​ = the strings that send an automaton AAA (states s1,…,sns_1, \dots, s_ns1​,…,sn​ , next-state function NNN ) from sis_isi​ to sjs_jsj​ without passing through an intermediate state shs_hsh​ with h>kh > kh>k .What is Li,j0L^0_{i,j}Li,j0​ , and which regular expression defines it?

    Li,j0={a∈I∣N(si,a)=sj}\boldsymbol{L^0_{i,j} = \{a \in I \mid N(s_i, a) = s_j\}}Li,j0​={a∈I∣N(si​,a)=sj​} , defined by a1∣a2∣⋯∣aMa_1 \mid a_2 \mid \dots \mid a_Ma1​∣a2​∣⋯∣aM​ for its elements a1,…,aMa_1, \dots, a_Ma1​,…,aM​ . Every state has index above 0, so these strings pass through no intermediate state: they are single input symbols. This is the base case of the induction.When i=ji = ji=j , the null string ε\varepsilonε also sends AAA from sis_isi​ to sis_isi​ , so ε\varepsilonε is added as…

  72. [Finite-State Automata] Li,jkL^k_{i,j}Li,jk​ = the strings that send an automaton AAA from sis_isi​ to sjs_jsj​ without passing through an intermediate state shs_hsh​ with h>kh > kh>k ; ri,jkr^k_{i,j}ri,jk​ is a regular expression defining Li,jkL^k_{i,j}Li,jk​ .How is ri,jk+1r^{k+1}_{i,j}ri,jk+1​ built from the rkr^krk 's?

    ri,jk+1=ri,jk∣ri,k+1k (rk+1,k+1k)∗ rk+1,jk\boldsymbol{r^{k+1}_{i,j} = r^k_{i,j} \mid r^k_{i,k+1}\,(r^k_{k+1,k+1})^*\,r^k_{k+1,j}}ri,jk+1​=ri,jk​∣ri,k+1k​(rk+1,k+1k​)∗rk+1,jk​ A string either avoids sk+1s_{k+1}sk+1​ , or splits into a first segment ( sis_isi​ to sk+1s_{k+1}sk+1​ ), any number of loops from sk+1s_{k+1}sk+1​ back to sk+1s_{k+1}sk+1​ , and a final segment ( sk+1s_{k+1}sk+1​ to sjs_jsj​ ), none of which passes through sk+1s_{k+1}sk+1​ in between. A path with two intermediate segment…

  73. [Finite-State Automata] For an automaton AAA with states s1,…,sns_1, \dots, s_ns1​,…,sn​ ( s1s_1s1​ initial), the regular expression r1,jnr^n_{1,j}r1,jn​ defines the set of all strings that send AAA from s1s_1s1​ to sjs_jsj​ .How does this give a regular expression for L(A)L(A)L(A) ?

    Join them with ∣|∣ over the accepting states: r=r1,j1n∣r1,j2n∣⋯∣r1,jmnr = r^n_{1,j_1} \mid r^n_{1,j_2} \mid \dots \mid r^n_{1,j_m}r=r1,j1​n​∣r1,j2​n​∣⋯∣r1,jm​n​ , where sj1,…,sjms_{j_1}, \dots, s_{j_m}sj1​​,…,sjm​​ are the accepting states. L(A)L(A)L(A) is the union of the sets L1,jnL^n_{1,j}L1,jn​ over the accepting states sjs_jsj​ , and LLL of a ∣|∣ -expression is the union of the languages.

  74. [Finite-State Automata] How does a nondeterministic finite-state automaton differ from a (deterministic) finite-state automaton?

    For a state and an input symbol, the next state is a subset of the states, possibly empty, instead of one state. Example: here N(s0,1)={s1,s2}N(s_0, 1) = \{s_1, s_2\}N(s0​,1)={s1​,s2​} and N(s0,0)=∅N(s_0, 0) = \emptysetN(s0​,0)=∅ .

  75. [Finite-State Automata] When does a nondeterministic finite-state automaton accept a string?

    When some sequence of next states, for the symbols of the string input from an initial state, ends in an accepting state. Example: this automaton, with N(s0,1)={s1,s2}N(s_0, 1) = \{s_1, s_2\}N(s0​,1)={s1​,s2​} and N(s0,0)=∅N(s_0, 0) = \emptysetN(s0​,0)=∅ , accepts exactly the strings that begin with 1.

  76. [Finite-State Automata] How is Part 2 of Kleene's theorem (regular expression ⇒\Rightarrow⇒ finite-state automaton) usually proved?

    Build a nondeterministic finite-state automaton for the regular expression (by a recursive algorithm), then a deterministic one accepting the same language.

  77. [Finite-State Automata] What is a regular language?

    A language defined by a regular expression, or equivalently (by Kleene's theorem) a language accepted by a finite-state automaton. Example: the strings of 0's and 1's ending in 010101 , defined by (0∣1)∗01(0 \mid 1)^*01(0∣1)∗01 .

  78. [Finite-State Automata] A finite-state automaton gets infinitely many input strings. Why must it return to some state over and over again?

    Pigeonhole principle: infinitely many strings, but only finitely many states, so some state is reached by infinitely many strings. This is what makes it possible to find languages that are not regular.

  79. [Finite-State Automata] L={akbk∣kL = \{a^kb^k \mid kL={akbk∣k a positive integer }\}} over {a,b}\{a, b\}{a,b} . Suppose a finite-state automaton AAA with states s1,…,sns_1, \dots, s_ns1​,…,sn​ accepts LLL .What does the pigeonhole principle give?

    Two strings apa^pap and aqa^qaq with p≠qp \ne qp=q that send AAA to the same state sms_msm​ . The pigeons are the infinitely many strings a,a2,a3,…a, a^2, a^3, \dotsa,a2,a3,… ; the pigeonholes are the nnn states.

  80. [Finite-State Automata] L={akbk∣kL = \{a^kb^k \mid kL={akbk∣k a positive integer }\}} . A finite-state automaton AAA accepting LLL would be sent to the same state sms_msm​ by apa^pap and aqa^qaq , with p≠qp \ne qp=q .What is the contradiction?

    aqbpa^qb^paqbp is accepted by AAA , but it is not in LLL . apbp∈La^pb^p \in Lapbp∈L , so from sms_msm​ the input bpb^pbp leads to an accepting state sas_asa​ . After aqa^qaq , AAA is also in sms_msm​ , so bpb^pbp again leads to sas_asa​ . So LLL is not regular. For p<qp < qp<q : the q−pq - pq−p extra aaa 's form a loop from sms_msm​ back to sms_msm​ .

  81. [Simplifying Finite-State Automata] Why is it worth replacing a finite-state automaton by one with fewer states that accepts the same language?

    Memory Storing an automaton with nnn states needs memory roughly proportional to n2n^2n2 . Example: about 10,000 memory spaces for 100 states, about 100 for 10 states. Programming The fewer states an automaton has, the easier it is to write a computer algorithm based on it. Example: automata produced during compiler construction are often larger than needed. Comparing automata To see whether two automata accept the same language, simplify each to a minimal number of states and compare the resul…

  82. [Simplifying Finite-State Automata] Which language does this automaton AAA accept (double circles are accepting states)?

    The strings of 0's and 1's that contain an even number of 1's. Each 1 moves AAA one step around the cycle s0→s1→s2→s3→s0s_0 \to s_1 \to s_2 \to s_3 \to s_0s0​→s1​→s2​→s3​→s0​ , and 0's leave the state unchanged; the accepting states s0,s2s_0, s_2s0​,s2​ are reached after an even number of 1's.Example: 0110 is accepted (ends in s2s_2s2​ ), 010 is not (ends in s1s_1s1​ ).

  83. [Simplifying Finite-State Automata] Which states of this automaton AAA can be combined without changing the language it accepts, and what is the resulting automaton?

    Combine s0s_0s0​ with s2s_2s2​ and s1s_1s1​ with s3s_3s3​ : a 2-state automaton that accepts the strings with an even number of 1's. This is the quotient automaton A‾\overline{A}A of AAA .

  84. [Simplifying Finite-State Automata] When states of an automaton are combined into sets of states, how are the arrows of the new transition diagram obtained?

    Each arrow from a state sss to a state ttt becomes an arrow, with the same label, from the combined state containing sss to the combined state containing ttt . Example: with combined states {s0,s2}\{s_0, s_2\}{s0​,s2​} and {s1,s3}\{s_1, s_3\}{s1​,s3​} , an arrow labeled 1 from s1s_1s1​ to s2s_2s2​ gives an arrow labeled 1 from {s1,s3}\{s_1, s_3\}{s1​,s3​} to {s0,s2}\{s_0, s_2\}{s0​,s2​} .

  85. [Simplifying Finite-State Automata] In mathematical terms, what does simplifying a finite-state automaton consist of?

    Defining an equivalence relation on the set of states and forming a new automaton whose states are the equivalence classes. Equivalent states are those that can be combined without affecting which input strings are accepted.

  86. [Simplifying Finite-State Automata] For a finite-state automaton AAA , what is the eventual-state function N∗N^*N∗ ?

    N∗(s,w)N^*(s, w)N∗(s,w) is the state AAA goes to if the characters of the string www are input in sequence when AAA is in state sss . Example: in an automaton where each 1 moves s0→s1→s2→s3→s0s_0 \to s_1 \to s_2 \to s_3 \to s_0s0​→s1​→s2​→s3​→s0​ and 0 changes nothing, N∗(s0,0110)=s2N^*(s_0, 0110) = s_2N∗(s0​,0110)=s2​ .

  87. [Simplifying Finite-State Automata] Let AAA be a finite-state automaton with eventual-state function N∗N^*N∗ . When are states sss and ttt ∗*∗ -equivalent ( s R∗ ts \, R_* \, tsR∗​t )?

    For all input strings www : N∗(s,w)N^*(s, w)N∗(s,w) is an accepting state ⇔\Leftrightarrow⇔ N∗(t,w)N^*(t, w)N∗(t,w) is an accepting state. Read "star equivalent". So every string accepted when AAA starts in sss is accepted when AAA starts in ttt , and conversely.Example: in an automaton that tracks the parity of the number of 1's with states s0,s1,s2,s3s_0, s_1, s_2, s_3s0​,s1​,s2​,s3​ (each 1 moves one step around the cycle, s0,s2s_0, s_2s0​,s2​ accepting), s0 R∗ s2s_0 \, R_* \, s_2s0​R∗​s2​ .

  88. [Simplifying Finite-State Automata] Why is ∗*∗ -equivalence R∗R_*R∗​ an equivalence relation on the set of states of an automaton?

    Its definition is " N∗(s,w)N^*(s, w)N∗(s,w) accepting ⇔\Leftrightarrow⇔ N∗(t,w)N^*(t, w)N∗(t,w) accepting for all www ", and ⇔\Leftrightarrow⇔ is reflexive, symmetric and transitive. Example: if s R∗ ts \, R_* \, tsR∗​t and t R∗ ut \, R_* \, utR∗​u , then for every www : N∗(s,w)N^*(s, w)N∗(s,w) accepting ⇔\Leftrightarrow⇔ N∗(t,w)N^*(t, w)N∗(t,w) accepting ⇔\Leftrightarrow⇔ N∗(u,w)N^*(u, w)N∗(u,w) accepting.

  89. [Simplifying Finite-State Automata] Why is it hard to decide whether two states are ∗*∗ -equivalent directly from the definition?

    The definition involves all input strings, and most languages have infinitely many, so they cannot be checked one by one. The practical method uses kkk -equivalence instead, which only involves strings of length at most kkk .

  90. [Simplifying Finite-State Automata] Let AAA be a finite-state automaton with eventual-state function N∗N^*N∗ and let k≥0k \ge 0k≥0 . When is state sss kkk -equivalent to state ttt ( s Rk ts \, R_k \, tsRk​t )?

    For all input strings www of length at most kkk , N∗(s,w)N^*(s, w)N∗(s,w) and N∗(t,w)N^*(t, w)N∗(t,w) are both accepting or both nonaccepting. Example: if s0,s1s_0, s_1s0​,s1​ are nonaccepting, N(s0,0)=s0N(s_0, 0) = s_0N(s0​,0)=s0​ , and N(s1,0)=s2N(s_1, 0) = s_2N(s1​,0)=s2​ is accepting, then s0s_0s0​ and s1s_1s1​ are 0-equivalent but not 1-equivalent (the string 0 separates them).

  91. [Simplifying Finite-State Automata] Which facts about kkk -equivalence of the states of a finite-state automaton follow directly from its definition?

    Equivalence relation For each k≥0k \ge 0k≥0 , kkk -equivalence is an equivalence relation. Example: s R0 ss \, R_0 \, ssR0​s for every state sss . Partition For each k≥0k \ge 0k≥0 , the kkk -equivalence classes partition the set of states into mutually disjoint subsets. Example: 0-equivalence classes {s0,s1,s4}\{s_0, s_1, s_4\}{s0​,s1​,s4​} (nonaccepting) and {s2,s3}\{s_2, s_3\}{s2​,s3​} (accepting). kkk -equivalent implies (k−1)(k-1)(k−1) -equivalent For k≥1k \ge 1k≥1 : strings of length at mo…

  92. [Simplifying Finite-State Automata] Theorem 12.3.1 Let AAA be a finite-state automaton with next-state function NNN , and sss , ttt states of AAA . When is sss 0-equivalent to ttt , and when (for k≥1k \ge 1k≥1 ) is sss kkk -equivalent to ttt ?

    0-equivalent ⇔\Leftrightarrow⇔ both accepting or both nonaccepting. kkk -equivalent ⇔\Leftrightarrow⇔ (k−1)(k-1)(k−1) -equivalent and N(s,m)N(s, m)N(s,m) , N(t,m)N(t, m)N(t,m) (k−1)(k-1)(k−1) -equivalent for every input symbol mmm . Example: if s,ts, ts,t are both nonaccepting with N(s,0)N(s, 0)N(s,0) accepting and N(t,0)N(t, 0)N(t,0) nonaccepting, then sss and ttt are 0-equivalent but not 1-equivalent.

  93. [Simplifying Finite-State Automata] For k≥1k \ge 1k≥1 : sss is kkk -equivalent to ttt ⇔\Leftrightarrow⇔ sss and ttt are (k−1)(k-1)(k−1) -equivalent and for every input symbol mmm , N(s,m)N(s, m)N(s,m) and N(t,m)N(t, m)N(t,m) are (k−1)(k-1)(k−1) -equivalent.What is the idea behind this theorem?

    Inputting a string www of length kkk has the same effect as inputting the first symbol mmm of www and then the remaining k−1k - 1k−1 symbols. So N∗(s,w)=N∗(N(s,m),w′)N^*(s, w) = N^*(N(s, m), w&#x27;)N∗(s,w)=N∗(N(s,m),w′) , where w=mw′w = mw&#x27;w=mw′ and w′w&#x27;w′ has length k−1k - 1k−1 .Example: N∗(s,011)=N∗(N(s,0),11)N^*(s, 011) = N^*(N(s, 0), 11)N∗(s,011)=N∗(N(s,0),11) .

  94. [Simplifying Finite-State Automata] How are the kkk -equivalence classes of the states of an automaton obtained from the (k−1)(k-1)(k−1) -equivalence classes ( k≥1k \ge 1k≥1 )?

    By subdividing each (k−1)(k-1)(k−1) -class: two states in it stay together exactly when, for every input symbol mmm , their next-states lie in the same (k−1)(k-1)(k−1) -class. Example: 0-class {s0,s1,s4}\{s_0, s_1, s_4\}{s0​,s1​,s4​} with N(s0,0)=s0N(s_0, 0) = s_0N(s0​,0)=s0​ (nonaccepting) but N(s1,0)=s2N(s_1, 0) = s_2N(s1​,0)=s2​ and N(s4,0)=s3N(s_4, 0) = s_3N(s4​,0)=s3​ (accepting) splits into {s0}\{s_0\}{s0​} and {s1,s4}\{s_1, s_4\}{s1​,s4​} .

  95. [Simplifying Finite-State Automata] Find the 0-equivalence classes of the states of this automaton (double circles are accepting states).

    {s0,s1,s4}\{s_0, s_1, s_4\}{s0​,s1​,s4​} and {s2,s3}\{s_2, s_3\}{s2​,s3​} States are 0-equivalent exactly when both are accepting or both are nonaccepting.

  96. [Simplifying Finite-State Automata] Why is s1s_1s1​ not 1-equivalent to s0s_0s0​ , but 1-equivalent to s4s_4s4​ ?

    Input 0 takes s0s_0s0​ to s0s_0s0​ but s1s_1s1​ to s2s_2s2​ , which are not 0-equivalent. For s1s_1s1​ and s4s_4s4​ the next-states are 0-equivalent for both inputs. s1,s4s_1, s_4s1​,s4​ : input 0 gives s2,s3s_2, s_3s2​,s3​ (both accepting), input 1 gives s4,s1s_4, s_1s4​,s1​ (both nonaccepting). 01s0s0s1s1s2s4s2s3s4s3s2s1s4s3s1\begin{array}{c|cc} & 0 & 1 \\ \hline s_0 & s_0 & s_1 \\ s_1 & s_2 & s_4 \\ s_2 & s_3 & s_4 \\ s_3 & s_2 & s_1 \\ s_4 & s_3 & s_1 \end{array}s0​s1​s2​s3​s4​​0s0​s2​s3​s2…

  97. [Simplifying Finite-State Automata] The 0-equivalence classes of this automaton are {s0,s1,s4}\{s_0, s_1, s_4\}{s0​,s1​,s4​} and {s2,s3}\{s_2, s_3\}{s2​,s3​} . Find the 1-equivalence classes and the 2-equivalence classes.

    Both are {s0}\{s_0\}{s0​} , {s1,s4}\{s_1, s_4\}{s1​,s4​} , {s2,s3}\{s_2, s_3\}{s2​,s3​} . s2,s3s_2, s_3s2​,s3​ : input 0 gives s3,s2s_3, s_2s3​,s2​ ; input 1 gives s4,s1s_4, s_1s4​,s1​ ; both pairs are 0-equivalent and also 1-equivalent. s1,s4s_1, s_4s1​,s4​ : input 0 gives s2,s3s_2, s_3s2​,s3​ ; input 1 gives s4,s1s_4, s_1s4​,s1​ ; both pairs are 1-equivalent, so s1 R2 s4s_1 \, R_2 \, s_4s1​R2​s4​ . 01s0s0s1s1s2s4s2s3s4s3s2s1s4s3s1\begin{array}{c|cc} & 0 & 1 \\ \hline s_0 & s_0 & s_1 \\ s_1 &…

  98. [Simplifying Finite-State Automata] Theorem 12.3.2 If AAA is a finite-state automaton, then for some integer K≥0K \ge 0K≥0 … ?

    The set of KKK -equivalence classes equals the set of (K+1)(K+1)(K+1) -equivalence classes, and for every such KKK both equal the set of ∗*∗ -equivalence classes. Example: an automaton whose 1-classes and 2-classes are both {s0}\{s_0\}{s0​} , {s1,s4}\{s_1, s_4\}{s1​,s4​} , {s2,s3}\{s_2, s_3\}{s2​,s3​} has exactly these ∗*∗ -classes.

  99. [Simplifying Finite-State Automata] Why does the subdivision of (k−1)(k-1)(k−1) -equivalence classes into kkk -equivalence classes eventually stop, with the final classes being the ∗*∗ -equivalence classes?

    Each step subdivides by the same rule, and there are finitely many states, so for some KKK the (K+1)(K+1)(K+1) -classes equal the KKK -classes. Since the rule only uses the current classes and the next-state function, every later step gives the same classes. So the states are mmm -equivalent for all mmm (hence ∗*∗ -equivalent) exactly when they are KKK -equivalent.

  100. [Simplifying Finite-State Automata] For the states of a finite-state automaton, the 1-equivalence classes equal the 2-equivalence classes. Can the 3-equivalence classes differ from them?

    No. The 3-classes are obtained from the 2-classes by the same rule that produced the 2-classes from the 1-classes, so they come out the same; and all of them equal the ∗*∗ -classes.