Ch.7: Different Forms of Grammars

Week 7 of the book "Automata, Formal Languages, and Turing Machines" by Emre Sermutlu (2020) 7.1. Simplifying Grammars 7.2. Chomsky Normal Form 7.3. Regular Grammars

60 flashcards · Computer Science · by lakesare

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

  1. [Simplifying Grammars] These two grammars generate the same language {02n1m0n∣n≥0, m≥1}\{0^{2n} 1^m 0^n \mid n \ge 0, \ m \ge 1\}{02n1m0n∣n≥0, m≥1} : S→00S0∣D∣BA→1A∣1B→0B∣BBC→0D∣B1D→A\begin{array}{rcl}S & \to & 00S0 \mid D \mid B \\ A & \to & 1A \mid 1 \\ B & \to & 0B \mid BB \\ C & \to & 0D \mid B1 \\ D & \to & A\end{array}SABCD​→→→→→​00S0∣D∣B1A∣10B∣BB0D∣B1A​ S→00S0∣AA→1A∣1\begin{array}{rcl}S & \to & 00S0 \mid A \\ A & \to & 1A \mid 1\end{array}SA​→→​00S0∣A1A∣1​ Why are BBB , CCC , DDD unneces…

    BBB is non-generating Every rule of BBB produces BBB again, so no string of terminals is ever derived from BBB . CCC is unreachable No derivation from SSS produces CCC . DDD only renames AAA DDD 's only rule is D→AD \to AD→A , so S→DS \to DS→D can be replaced by S→AS \to AS→A .

  2. [Simplifying Grammars] What is a useless symbol in a grammar?

    A symbol (variable or terminal) that is used in no derivation of a string of terminals from the start variable. Removing all productions that contain useless symbols does not change the language.

  3. [Simplifying Grammars] When is a variable XXX reachable in a grammar with start variable SSS ?

    Some derivation starting from SSS produces a string containing XXX . Example: in S→0AS \to 0AS→0A , A→1A \to 1A→1 , B→0B \to 0B→0 , the variable AAA is reachable and BBB is not.

  4. [Simplifying Grammars] When is a variable XXX non-generating?

    No string of terminals can be derived from XXX . Example: D→0D0∣ADD \to 0D0 \mid ADD→0D0∣AD is non-generating, since every rule produces DDD again.

  5. [Simplifying Grammars] What are the two types of useless symbols XXX ?

    Type 1: XXX is not reachable No derivation starting from the start variable produces XXX . Type 2: no string containing XXX ever gives a string of terminals (a) XXX is non-generating, or (b) every intermediate string containing XXX also contains a non-generating symbol. Example of 2b: with A→EDA \to EDA→ED , E→101E \to 101E→101 and DDD non-generating, EEE is reachable and generating but useless.

  6. [Simplifying Grammars] In this grammar, why are CCC , DDD and EEE useless? S→0S0∣A∣B∣DA→1A0∣1∣EDB→0B1∣ε∣DEDC→01S∣ABD→0D0∣ADE→101∣010\begin{array}{rcl}S & \to & 0S0 \mid A \mid B \mid D \\ A & \to & 1A0 \mid 1 \mid ED \\ B & \to & 0B1 \mid \varepsilon \mid DED \\ C & \to & 01S \mid AB \\ D & \to & 0D0 \mid AD \\ E & \to & 101 \mid 010\end{array}SABCDE​→→→→→→​0S0∣A∣B∣D1A0∣1∣ED0B1∣ε∣DED01S∣AB0D0∣AD101∣010​

    CCC Unreachable: CCC is on no right-hand side. DDD Non-generating: both rules of DDD produce DDD again. EEE Reachable and generating, but EEE only appears together with DDD ( EDEDED , DEDDEDDED ), so every string containing EEE contains the non-generating DDD . After removing them: S→0S0∣A∣BS \to 0S0 \mid A \mid BS→0S0∣A∣B , A→1A0∣1\ A \to 1A0 \mid 1 A→1A0∣1 , B→0B1∣ε\ B \to 0B1 \mid \varepsilon B→0B1∣ε .

  7. [Simplifying Grammars] A production that contains a useless symbol is called a useless production.

  8. [Simplifying Grammars] In which order do you eliminate useless symbols?

    1. Eliminate non-generating symbols. 2. Eliminate unreachable symbols. Step 1 makes the type 2b symbols (those always next to a non-generating symbol) unreachable, so step 2 removes them.

  9. [Simplifying Grammars] Why can eliminating unreachable symbols first and non-generating symbols second leave useless symbols?

    Removing non-generating symbols can create new unreachable symbols. Example: in S→0S0∣A∣B∣DS \to 0S0 \mid A \mid B \mid DS→0S0∣A∣B∣D , A→1A0∣1∣EDA \to 1A0 \mid 1 \mid EDA→1A0∣1∣ED , B→0B1∣ε∣DEDB \to 0B1 \mid \varepsilon \mid DEDB→0B1∣ε∣DED , D→0D0∣ADD \to 0D0 \mid ADD→0D0∣AD , E→101E \to 101E→101 : removing the non-generating DDD deletes A→EDA \to EDA→ED and B→DEDB \to DEDB→DED , and only then EEE is unreachable.With that order a third step (unreachables again) is needed.

  10. [Simplifying Grammars] Eliminate all useless symbols and productions: S→0S1∣SS∣BD∣ABC∣εA→00∣1∣S∣CDB→0B∣DD∣ADAC→010∣101D→D11∣BE→1S1∣ESE\begin{array}{rcl}S & \to & 0S1 \mid SS \mid BD \mid ABC \mid \varepsilon \\ A & \to & 00 \mid 1 \mid S \mid CD \\ B & \to & 0B \mid DD \mid ADA \\ C & \to & 010 \mid 101 \\ D & \to & D11 \mid B \\ E & \to & 1S1 \mid ESE\end{array}SABCDE​→→→→→→​0S1∣SS∣BD∣ABC∣ε00∣1∣S∣CD0B∣DD∣ADA010∣101D11∣B1S1∣ESE​

    S→0S1∣SS∣ε\boldsymbol{S \to 0S1 \mid SS \mid \varepsilon}S→0S1∣SS∣ε BBB and DDD are non-generating (every rule of BBB or DDD contains BBB or DDD ). Removing them leaves AAA , CCC , EEE unreachable ( AAA and CCC appeared only in S→ABCS \to ABCS→ABC and A→CDA \to CDA→CD ; EEE was never reachable).

  11. [Simplifying Grammars] What is a unit production?

    A production A→BA \to BA→B where both AAA and BBB are variables. A→aA \to aA→a with a terminal aaa is not a unit production.

  12. [Simplifying Grammars] Why are unit productions unwanted?

    They increase the number of steps in a derivation without producing anything.

  13. [Simplifying Grammars] B→X1∣X2∣⋯∣XnB \to X_1 \mid X_2 \mid \dots \mid X_nB→X1​∣X2​∣⋯∣Xn​ are all the productions of BBB (each XiX_iXi​ a string of variables and terminals). How do you eliminate the unit production A→BA \to BA→B ?

    Replace A→BA \to BA→B by A→X1∣X2∣⋯∣XnA \to X_1 \mid X_2 \mid \dots \mid X_nA→X1​∣X2​∣⋯∣Xn​ . Example: S→0A0∣BS \to 0A0 \mid BS→0A0∣B , A→BB∣01A \to BB \mid 01A→BB∣01 , B→0∣1AB \to 0 \mid 1AB→0∣1A becomes S→0A0∣0∣1AS \to 0A0 \mid 0 \mid 1AS→0A0∣0∣1A , A→BB∣01A \to BB \mid 01A→BB∣01 , B→0∣1AB \to 0 \mid 1AB→0∣1A .

  14. [Simplifying Grammars] When eliminating unit productions, why first find all variables reachable from each variable by unit productions?

    Removing one unit production can create new ones, e.g. with A→BA \to BA→B and B→CB \to CB→C , replacing A→BA \to BA→B creates A→CA \to CA→C . So for each AAA collect every variable reachable from AAA by unit productions, give AAA all their non-unit productions, and remove all unit productions in one step.

  15. [Simplifying Grammars] Eliminate all unit productions: S→0S0∣AA→101∣BB→C∣1C→1∣111∣A\begin{array}{rcl}S & \to & 0S0 \mid A \\ A & \to & 101 \mid B \\ B & \to & C \mid 1 \\ C & \to & 1 \mid 111 \mid A\end{array}SABC​→→→→​0S0∣A101∣BC∣11∣111∣A​

    Every variable gets 101∣1∣111101 \mid 1 \mid 111101∣1∣111 ; then A,B,CA, B, CA,B,C are unreachable: S→0S0∣101∣1∣111\ \boldsymbol{S \to 0S0 \mid 101 \mid 1 \mid 111} S→0S0∣101∣1∣111 Non-unit productions: S→0S0S \to 0S0S→0S0 , A→101A \to 101A→101 , B→1B \to 1B→1 , C→1∣111C \to 1 \mid 111C→1∣111 . By unit productions SSS reaches A,B,CA, B, CA,B,C ; AAA reaches B,CB, CB,C ; BBB reaches A,CA, CA,C ; CCC reaches A,BA, BA,B .

  16. [Simplifying Grammars] Why do we prefer grammars without ε\varepsilonε -productions ( A→εA \to \varepsilonA→ε )?

    Without them, the length of the intermediate string never decreases during a derivation. With ε\varepsilonε -productions the length can go up and down, which makes the theoretical analysis of derivations much harder.

  17. [Simplifying Grammars] When is it impossible to eliminate all ε\varepsilonε -productions from a grammar for LLL ?

    When ε∈L\varepsilon \in Lε∈L : then S→εS \to \varepsilonS→ε must stay (all other ε\varepsilonε -productions can be eliminated).

  18. [Simplifying Grammars] When is a variable AAA nullable?

    ε\varepsilonε can be derived from AAA . Example: with A→εA \to \varepsilonA→ε , B→εB \to \varepsilonB→ε , C→ABC \to ABC→AB , all of AAA , BBB , CCC are nullable.

  19. [Simplifying Grammars] How do you eliminate ε\varepsilonε -productions from a grammar?

    For each occurrence of a nullable variable on a right-hand side, add a rule without that occurrence; then delete the rules A→εA \to \varepsilonA→ε . Keep S→εS \to \varepsilonS→ε only if ε\varepsilonε is in the language.Example: S→0S0∣1A1S \to 0S0 \mid 1A1S→0S0∣1A1 , A→000∣εA \to 000 \mid \varepsilonA→000∣ε becomes S→0S0∣1A1∣11S \to 0S0 \mid 1A1 \mid 11S→0S0∣1A1∣11 , A→000A \to 000A→000 .

  20. [Simplifying Grammars] A→000∣εA \to 000 \mid \varepsilonA→000∣ε . After eliminating ε\varepsilonε -productions, which rules replace S→1A0A1S \to 1A0A1S→1A0A1 ?

    S→1A0A1∣10A1∣1A01∣101\boldsymbol{S \to 1A0A1 \mid 10A1 \mid 1A01 \mid 101}S→1A0A1∣10A1∣1A01∣101 Each of the two occurrences of AAA can be kept or left out: 22=42^2 = 422=4 rules.

  21. [Simplifying Grammars] Eliminate the ε\varepsilonε -productions: S→0S∣B∣00CA→111∣CC∣εB→A101C∣1C→11∣A\begin{array}{rcl}S & \to & 0S \mid B \mid 00C \\ A & \to & 111 \mid CC \mid \varepsilon \\ B & \to & A101C \mid 1 \\ C & \to & 11 \mid A\end{array}SABC​→→→→​0S∣B∣00C111∣CC∣εA101C∣111∣A​

    AAA and CCC are nullable: S→0S∣B∣00C∣00A→111∣CC∣CB→A101C∣101C∣A101∣101∣1C→11∣A\begin{array}{rcl}S & \to & 0S \mid B \mid 00C \mid 00 \\ A & \to & 111 \mid CC \mid C \\ B & \to & A101C \mid 101C \mid A101 \mid 101 \mid 1 \\ C & \to & 11 \mid A\end{array}SABC​→→→→​0S∣B∣00C∣00111∣CC∣CA101C∣101C∣A101∣101∣111∣A​ CCC is nullable because C→AC \to AC→A . From A→CCA \to CCA→CC , leaving out one CCC gives A→CA \to CA→C ; leaving out both gives A→εA \to \varepsilonA→ε , which is not added.

  22. [Simplifying Grammars] Eliminate the ε\varepsilonε -productions: S→0S∣ABA→1∣11∣εB→0∣00∣AAA∣ε\begin{array}{rcl}S & \to & 0S \mid AB \\ A & \to & 1 \mid 11 \mid \varepsilon \\ B & \to & 0 \mid 00 \mid AAA \mid \varepsilon\end{array}SAB​→→→​0S∣AB1∣11∣ε0∣00∣AAA∣ε​

    All three variables are nullable, so S→εS \to \varepsilonS→ε must stay: S→0S∣0∣AB∣A∣B∣εA→1∣11B→0∣00∣AAA∣AA∣A\begin{array}{rcl}S & \to & 0S \mid 0 \mid AB \mid A \mid B \mid \varepsilon \\ A & \to & 1 \mid 11 \\ B & \to & 0 \mid 00 \mid AAA \mid AA \mid A\end{array}SAB​→→→​0S∣0∣AB∣A∣B∣ε1∣110∣00∣AAA∣AA∣A​ ε\varepsilonε is in the language, since S→AB→εS \to AB \to \varepsilonS→AB→ε .

  23. [Simplifying Grammars] In which order do you apply the three simplifications (removing ε\varepsilonε -productions, unit productions, useless symbols) so that none of them is left?

    1. ε\varepsilonε -productions, 2. unit productions, 3. useless symbols. Each step can create unwanted productions only of a kind that a later step removes.

  24. [Simplifying Grammars] Why must unit productions be eliminated before useless symbols?

    Eliminating unit productions can make a variable unreachable. Example: S→0A0S \to 0A0S→0A0 , A→1∣BA \to 1 \mid BA→1∣B , B→10∣01B \to 10 \mid 01B→10∣01 has no useless symbols. Eliminating the unit production gives A→1∣10∣01A \to 1 \mid 10 \mid 01A→1∣10∣01 , and now BBB is unreachable.

  25. [Simplifying Grammars] Why must ε\varepsilonε -productions be eliminated before unit productions?

    Eliminating ε\varepsilonε -productions can create unit productions. Example: S→ABS \to ABS→AB , A→0A \to 0A→0 , B→1∣εB \to 1 \mid \varepsilonB→1∣ε has no unit productions. Removing B→εB \to \varepsilonB→ε adds S→AS \to AS→A .

  26. [Simplifying Grammars] Eliminate all ε\varepsilonε -productions, unit productions and useless symbols: S→BABA→a∣aAB→bb∣C∣εC→aC∣CC∣DCD→SA∣AB\begin{array}{rcl}S & \to & BAB \\ A & \to & a \mid aA \\ B & \to & bb \mid C \mid \varepsilon \\ C & \to & aC \mid CC \mid DC \\ D & \to & SA \mid AB\end{array}SABCD​→→→→→​BABa∣aAbb∣C∣εaC∣CC∣DCSA∣AB​

    CCC is non-generating, and after removing it DDD is unreachable: S→BAB∣BA∣AB∣a∣aAA→a∣aAB→bb\begin{array}{rcl}S & \to & BAB \mid BA \mid AB \mid a \mid aA \\ A & \to & a \mid aA \\ B & \to & bb\end{array}SAB​→→→​BAB∣BA∣AB∣a∣aAa∣aAbb​ ε\varepsilonε -step ( BBB nullable): S→BAB∣BA∣AB∣AS \to BAB \mid BA \mid AB \mid AS→BAB∣BA∣AB∣A , D→SA∣AB∣AD \to SA \mid AB \mid AD→SA∣AB∣A . Unit step: S→AS \to AS→A , B→CB \to CB→C , D→AD \to AD→A are replaced. Then every rule of CCC contains CCC , and DDD appeare…

  27. [Simplifying Grammars] Eliminate all ε\varepsilonε -productions, unit productions and useless symbols: S→AA∣0D0A→ACB→0∣1C→111∣AD∣εD→1∣C\begin{array}{rcl}S & \to & AA \mid 0D0 \\ A & \to & AC \\ B & \to & 0 \mid 1 \\ C & \to & 111 \mid AD \mid \varepsilon \\ D & \to & 1 \mid C\end{array}SABCD​→→→→→​AA∣0D0AC0∣1111∣AD∣ε1∣C​

    S→0D0∣00,D→1∣111\boldsymbol{S \to 0D0 \mid 00, \quad D \to 1 \mid 111}S→0D0∣00,D→1∣111 ε\varepsilonε -step ( CCC , DDD nullable): S→AA∣0D0∣00S \to AA \mid 0D0 \mid 00S→AA∣0D0∣00 , C→111∣AD∣AC \to 111 \mid AD \mid AC→111∣AD∣A . Unit step ( D→CD \to CD→C , C→AC \to AC→A , D→AD \to AD→A ): C→111∣AD∣ACC \to 111 \mid AD \mid ACC→111∣AD∣AC , D→1∣111∣AD∣ACD \to 1 \mid 111 \mid AD \mid ACD→1∣111∣AD∣AC .Useless: AAA is non-generating ( A→ACA \to ACA→AC only), BBB is unreachable, and after removing AAA ,…

  28. [Chomsky Normal Form] When is a context-free grammar in Chomsky Normal Form (CNF)?

    Every production is A→BCA \to BCA→BC or A→aA \to aA→a ( A,B,CA, B, CA,B,C variables, BBB and CCC not the start variable, aaa a terminal), plus S→εS \to \varepsilonS→ε if and only if ε\varepsilonε is in the language. Example: S→AB∣AAS \to AB \mid AAS→AB∣AA , A→aA \to aA→a , B→BC∣CC∣bB \to BC \mid CC \mid bB→BC∣CC∣b , C→a∣cC \to a \mid cC→a∣c .

  29. [Chomsky Normal Form] Is this grammar ( SSS the start variable) in Chomsky Normal Form? S→TU∣a∣εT→UU∣TU∣UTU→TT∣a∣b∣c\begin{array}{rcl}S & \to & TU \mid a \mid \varepsilon \\ T & \to & UU \mid TU \mid UT \\ U & \to & TT \mid a \mid b \mid c\end{array}STU​→→→​TU∣a∣εUU∣TU∣UTTT∣a∣b∣c​

    Yes. Every rule is (variable)(variable) or a single terminal, SSS is on no right-hand side, and S→εS \to \varepsilonS→ε is allowed for the start variable.

  30. [Chomsky Normal Form] Why is this grammar not in Chomsky Normal Form? S→ABA∣AAA→aB→b\begin{array}{rcl}S & \to & ABA \mid AA \\ A & \to & a \\ B & \to & b\end{array}SAB​→→→​ABA∣AAab​

    S→ABAS \to ABAS→ABA has three variables on the right-hand side.

  31. [Chomsky Normal Form] Why is this grammar not in Chomsky Normal Form? S→AB∣BA→aAB→b\begin{array}{rcl}S & \to & AB \mid B \\ A & \to & aA \\ B & \to & b\end{array}SAB​→→→​AB∣BaAb​

    S→BS \to BS→B is a unit production, and A→aAA \to aAA→aA mixes a terminal with a variable.

  32. [Chomsky Normal Form] Why is this grammar ( SSS the start variable) not in Chomsky Normal Form? S→TT∣aT→ST∣b\begin{array}{rcl}S & \to & TT \mid a \\ T & \to & ST \mid b\end{array}ST​→→​TT∣aST∣b​

    The start variable SSS appears on a right-hand side ( T→STT \to STT→ST ).

  33. [Chomsky Normal Form] Why is this grammar not in Chomsky Normal Form? S→TT∣aT→a∣b∣ε\begin{array}{rcl}S & \to & TT \mid a \\ T & \to & a \mid b \mid \varepsilon\end{array}ST​→→​TT∣aa∣b∣ε​

    T→εT \to \varepsilonT→ε : only the start variable may have an ε\varepsilonε -production.

  34. [Chomsky Normal Form] In a grammar in Chomsky Normal Form, how many steps does the derivation of a string of length n≥1n \ge 1n≥1 take?

    2n−1\boldsymbol{2n - 1}2n−1 n−1n - 1n−1 steps A→BCA \to BCA→BC (each adds one variable, from 1 to nnn ) and nnn steps A→aA \to aA→a (one per terminal).Example: S→AT→ABC→aBC→abC→abcS \to AT \to ABC \to aBC \to abC \to abcS→AT→ABC→aBC→abC→abc , 5 steps for abcabcabc .

  35. [Chomsky Normal Form] What does the theorem about Chomsky Normal Form say?

    Every context-free language is generated by a context-free grammar in Chomsky Normal Form.

  36. [Chomsky Normal Form] What are the three steps of converting a context-free grammar to Chomsky Normal Form?

    Simplify Eliminate all ε\varepsilonε -productions and unit productions (eliminating useless symbols is optional), and add a new start variable if necessary. Eliminate terminals in long right-hand sides Except in rules A→aA \to aA→a , replace each terminal by a new variable with a single rule. Example: S→0A0S \to 0A0S→0A0 becomes S→ZAZS \to ZAZS→ZAZ with Z→0Z \to 0Z→0 . Break long right-hand sides Replace right-hand sides with more than 2 variables using new variables. Example: S→ZAZS \to ZAZS→Z…

  37. [Chomsky Normal Form] When converting to Chomsky Normal Form, when is a new start variable S0S_0S0​ needed, and what is its rule?

    When the start variable SSS appears on a right-hand side; add S0→SS_0 \to SS0​→S (then remove that unit production as usual). In CNF, the start variable may not appear on a right-hand side.

  38. [Chomsky Normal Form] Convert to Chomsky Normal Form: S→0A0∣1BA→1∣BBB→111∣A0\begin{array}{rcl}S & \to & 0A0 \mid 1B \\ A & \to & 1 \mid BB \\ B & \to & 111 \mid A0\end{array}SAB​→→→​0A0∣1B1∣BB111∣A0​

    W→1W \to 1W→1 , Z→0Z \to 0Z→0 replace terminals; CCC , DDD break long right-hand sides: S→ZC∣WBA→1∣BBB→WD∣AZC→AZD→WWW→1Z→0\begin{array}{rcl}S & \to & ZC \mid WB \\ A & \to & 1 \mid BB \\ B & \to & WD \mid AZ \\ C & \to & AZ \\ D & \to & WW \\ W & \to & 1 \\ Z & \to & 0\end{array}SABCDWZ​→→→→→→→​ZC∣WB1∣BBWD∣AZAZWW10​ No ε\varepsilonε -productions, unit productions or useless symbols, and SSS is on no right-hand side, so no new start variable. Intermediate step: S→ZAZ∣WBS \to ZAZ \mid WBS→ZAZ∣WB…

  39. [Chomsky Normal Form] Convert to Chomsky Normal Form: S→A1AA→0B0∣εB→A∣10\begin{array}{rcl}S & \to & A1A \\ A & \to & 0B0 \mid \varepsilon \\ B & \to & A \mid 10\end{array}SAB​→→→​A1A0B0∣εA∣10​

    After removing ε\varepsilonε - and unit productions, replacing terminals ( W→1W \to 1W→1 , Z→0Z \to 0Z→0 ) and breaking long right-hand sides: S→AC∣WA∣AW∣1A→ZD∣ZE∣ZZB→WZC→WAD→BZE→AZW→1Z→0\begin{array}{rcl}S & \to & AC \mid WA \mid AW \mid 1 \\ A & \to & ZD \mid ZE \mid ZZ \\ B & \to & WZ \\ C & \to & WA \\ D & \to & BZ \\ E & \to & AZ \\ W & \to & 1 \\ Z & \to & 0\end{array}SABCDEWZ​→→→→→→→→​AC∣WA∣AW∣1ZD∣ZE∣ZZWZWABZAZ10​ After the first step: S→A1A∣1A∣A1∣1S \to A1A \mid 1A \mid A1 \mid 1S→A1A∣1…

  40. [Chomsky Normal Form] Give a grammar in Chomsky Normal Form for {w∈{a,b}∗∣∣w∣=8k, k=1,2,3,… }\{w \in \{a, b\}^* \mid |w| = 8k, \ k = 1, 2, 3, \dots\}{w∈{a,b}∗∣∣w∣=8k, k=1,2,3,…} without introducing 7 new variables for D8D^8D8 .

    Double the length at each level: S→AA∣BBA→AA∣BBB→CCC→DDD→a∣b\begin{array}{rcl}S & \to & AA \mid BB \\ A & \to & AA \mid BB \\ B & \to & CC \\ C & \to & DD \\ D & \to & a \mid b\end{array}SABCD​→→→→→​AA∣BBAA∣BBCCDDa∣b​ DDD gives strings of length 1, CCC of length 2, BBB of length 4, BBBBBB of length 8, and AAA of every positive multiple of 8.A first grammar before conversion: S→A∣ASS \to A \mid ASS→A∣AS , A→DDDDDDDDA \to DDDDDDDDA→DDDDDDDD , D→a∣bD \to a \mid bD→a∣b .

  41. [Regular Grammars] What is a regular grammar?

    A grammar where every production is A→aBA \to aBA→aB or A→aA \to aA→a ( A,BA, BA,B variables, aaa a terminal); A→εA \to \varepsilonA→ε is also allowed. Example: S→1A∣εS \to 1A \mid \varepsilonS→1A∣ε , A→0SA \to 0SA→0S .

  42. [Regular Grammars] Which language does the regular grammar S→1A∣εS \to 1A \mid \varepsilonS→1A∣ε , A→0SA \to 0SA→0S generate?

    (10)∗\boldsymbol{(10)^*}(10)∗ Each pass S→1A→10SS \to 1A \to 10SS→1A→10S adds 101010 ; S→εS \to \varepsilonS→ε ends the derivation.

  43. [Regular Grammars] What does the theorem about regular grammars and regular languages say?

    A language is regular if and only if it is generated by a regular grammar.

  44. [Regular Grammars] How does the proof turn a regular grammar into an NFA?

    Each variable is a state; one extra, unique accept state is added. A→aBA \to aBA→aB : transition from AAA to BBB on aaa . A→aA \to aA→a : transition from AAA to the accept state on aaa . A→εA \to \varepsilonA→ε : ε\varepsilonε -transition from AAA to the accept state. The start variable is the start state.

  45. [Regular Grammars] Draw the NFA for the regular grammar S→0AS \to 0AS→0A , A→1BA \to 1BA→1B , B→0∣1AB \to 0 \mid 1AB→0∣1A . Which language is it?

    0(11)∗10\boldsymbol{0(11)^*10}0(11)∗10 States S,A,BS, A, BS,A,B and an extra accept state; B→0B \to 0B→0 is the transition to the accept state on 000 .

  46. [Regular Grammars] Find a regular grammar for (a∪bab)c+(b∪c)∗(a \cup bab)c^+(b \cup c)^*(a∪bab)c+(b∪c)∗ over Σ={a,b,c}\Sigma = \{a, b, c\}Σ={a,b,c} .

    S→aA∣bB, A→cA∣cD, B→aC, C→bA, D→bD∣cD∣ε\boldsymbol{S \to aA \mid bB, \ A \to cA \mid cD, \ B \to aC, \ C \to bA, \ D \to bD \mid cD \mid \varepsilon}S→aA∣bB, A→cA∣cD, B→aC, C→bA, D→bD∣cD∣ε SSS produces aaa or babbabbab (through BBB , CCC ) before AAA ; AAA produces c+c^+c+ before DDD ; DDD produces (b∪c)∗(b \cup c)^*(b∪c)∗ .

  47. [Regular Grammars] How do you read a regular grammar off this NFA (start state SSS )?

    Each transition from XXX to YYY on aaa gives X→aYX \to aYX→aY ; each ε\varepsilonε -transition from XXX to an accept state gives X→εX \to \varepsilonX→ε . S→aA∣bBS \to aA \mid bBS→aA∣bB , A→cA∣cDA \to cA \mid cDA→cA∣cD , B→aCB \to aCB→aC , C→bAC \to bAC→bA , D→bD∣cD∣εD \to bD \mid cD \mid \varepsilonD→bD∣cD∣ε , for the language (a∪bab)c+(b∪c)∗(a \cup bab)c^+(b \cup c)^*(a∪bab)c+(b∪c)∗ .

  48. [Exercises] Eliminate all useless symbols and productions: S→0S00∣1∣AA→1B11∣BBB→0B0∣BCBC→00∣1S1\begin{array}{rcl}S & \to & 0S00 \mid 1 \mid A \\ A & \to & 1B11 \mid BB \\ B & \to & 0B0 \mid BCB \\ C & \to & 00 \mid 1S1\end{array}SABC​→→→→​0S00∣1∣A1B11∣BB0B0∣BCB00∣1S1​

    S→0S00∣1\boldsymbol{S \to 0S00 \mid 1}S→0S00∣1 BBB is non-generating (every rule contains BBB ), so AAA is too. CCC appears only in a rule of BBB , so after removing BBB it is unreachable.

  49. [Exercises] Eliminate all useless symbols and productions: S→aaS∣C∣DA→aSbb∣BB→bB∣aCa∣εC→b∣bb∣bbbD→aDa∣CBD\begin{array}{rcl}S & \to & aaS \mid C \mid D \\ A & \to & aSbb \mid B \\ B & \to & bB \mid aCa \mid \varepsilon \\ C & \to & b \mid bb \mid bbb \\ D & \to & aDa \mid CBD\end{array}SABCD​→→→→→​aaS∣C∣DaSbb∣BbB∣aCa∣εb∣bb∣bbbaDa∣CBD​

    S→aaS∣C,C→b∣bb∣bbb\boldsymbol{S \to aaS \mid C, \quad C \to b \mid bb \mid bbb}S→aaS∣C,C→b∣bb∣bbb DDD is non-generating (every rule contains DDD ). AAA is on no right-hand side, so unreachable; BBB appears only in rules of AAA and DDD , so after removing them BBB is unreachable.

  50. [Exercises] Eliminate the unit productions (and the variables that become useless): S→0∣A∣11CA→10∣01∣BB→0110C→00∣B\begin{array}{rcl}S & \to & 0 \mid A \mid 11C \\ A & \to & 10 \mid 01 \mid B \\ B & \to & 0110 \\ C & \to & 00 \mid B\end{array}SABC​→→→→​0∣A∣11C10∣01∣B011000∣B​

    S→0∣10∣01∣0110∣11C,C→00∣0110\boldsymbol{S \to 0 \mid 10 \mid 01 \mid 0110 \mid 11C, \quad C \to 00 \mid 0110}S→0∣10∣01∣0110∣11C,C→00∣0110 SSS reaches AAA and BBB by unit productions, CCC reaches BBB . Afterwards AAA and BBB are unreachable.

  51. [Exercises] Eliminate the ε\varepsilonε -productions: S→aA∣BaBA→aaa∣BB→bB∣ε\begin{array}{rcl}S & \to & aA \mid BaB \\ A & \to & aaa \mid B \\ B & \to & bB \mid \varepsilon\end{array}SAB​→→→​aA∣BaBaaa∣BbB∣ε​

    BBB and AAA are nullable ( A→BA \to BA→B ): S→aA∣a∣BaB∣aB∣BaA→aaa∣BB→bB∣b\begin{array}{rcl}S & \to & aA \mid a \mid BaB \mid aB \mid Ba \\ A & \to & aaa \mid B \\ B & \to & bB \mid b\end{array}SAB​→→→​aA∣a∣BaB∣aB∣Baaaa∣BbB∣b​ From BaBBaBBaB , leaving out one or both BBB gives aBaBaB , BaBaBa , aaa . SSS is not nullable, so no S→εS \to \varepsilonS→ε .

  52. [Exercises] Eliminate the ε\varepsilonε -productions: S→SA∣A11B1A→000∣εB→00∣ε\begin{array}{rcl}S & \to & SA \mid A11B1 \\ A & \to & 000 \mid \varepsilon \\ B & \to & 00 \mid \varepsilon\end{array}SAB​→→→​SA∣A11B1000∣ε00∣ε​

    S→SA∣A11B1∣11B1∣A111∣111, A→000, B→00\boldsymbol{S \to SA \mid A11B1 \mid 11B1 \mid A111 \mid 111, \ A \to 000, \ B \to 00}S→SA∣A11B1∣11B1∣A111∣111, A→000, B→00 Leaving out AAA in SASASA gives S→SS \to SS→S , which is dropped.

  53. [Exercises] Eliminate all useless, unit and ε\varepsilonε -productions: S→aaA∣BC∣aDaDA→b∣B∣εB→b∣babC→aC∣CCD→a∣A∣C\begin{array}{rcl}S & \to & aaA \mid BC \mid aDaD \\ A & \to & b \mid B \mid \varepsilon \\ B & \to & b \mid bab \\ C & \to & aC \mid CC \\ D & \to & a \mid A \mid C\end{array}SABCD​→→→→→​aaA∣BC∣aDaDb∣B∣εb∣babaC∣CCa∣A∣C​

    AAA , DDD nullable; CCC non-generating; BBB unreachable: S→aa∣aaA∣aaD∣aDa∣aDaDA→b∣babD→a∣b∣bab\begin{array}{rcl}S & \to & aa \mid aaA \mid aaD \mid aDa \mid aDaD \\ A & \to & b \mid bab \\ D & \to & a \mid b \mid bab\end{array}SAD​→→→​aa∣aaA∣aaD∣aDa∣aDaDb∣baba∣b∣bab​ DDD is nullable because D→AD \to AD→A . Every rule of CCC contains CCC ; removing CCC deletes S→BCS \to BCS→BC , and after the unit productions A→BA \to BA→B , D→AD \to AD→A are replaced, BBB is on no right-hand side.

  54. [Exercises] Eliminate all useless, unit and ε\varepsilonε -productions: S→01S∣AA→01∣BCB→010C→CC∣εD→0C1C∣ε\begin{array}{rcl}S & \to & 01S \mid A \\ A & \to & 01 \mid BC \\ B & \to & 010 \\ C & \to & CC \mid \varepsilon \\ D & \to & 0C1C \mid \varepsilon\end{array}SABCD​→→→→→​01S∣A01∣BC010CC∣ε0C1C∣ε​

    S→01S∣01∣010\boldsymbol{S \to 01S \mid 01 \mid 010}S→01S∣01∣010 CCC is nullable, so A→BC∣BA \to BC \mid BA→BC∣B . After the unit productions, C→CCC \to CCC→CC is the only rule of CCC : non-generating. DDD is unreachable, and AAA , BBB become unreachable.

  55. [Exercises] Convert to Chomsky Normal Form: S→A∣AB∣ABAAA→0B→1\begin{array}{rcl}S & \to & A \mid AB \mid ABAA \\ A & \to & 0 \\ B & \to & 1\end{array}SAB​→→→​A∣AB∣ABAA01​

    S→0∣AB∣CD, C→AB, D→AA, A→0, B→1\boldsymbol{S \to 0 \mid AB \mid CD, \ C \to AB, \ D \to AA, \ A \to 0, \ B \to 1}S→0∣AB∣CD, C→AB, D→AA, A→0, B→1

  56. [Exercises] Convert to Chomsky Normal Form: S→AA∣ABA→0∣εB→1∣ε\begin{array}{rcl}S & \to & AA \mid AB \\ A & \to & 0 \mid \varepsilon \\ B & \to & 1 \mid \varepsilon\end{array}SAB​→→→​AA∣AB0∣ε1∣ε​

    S→AA∣AB∣0∣1∣ε, A→0, B→1\boldsymbol{S \to AA \mid AB \mid 0 \mid 1 \mid \varepsilon, \ A \to 0, \ B \to 1}S→AA∣AB∣0∣1∣ε, A→0, B→1 SSS is nullable, so S→εS \to \varepsilonS→ε stays; the new unit productions S→AS \to AS→A , S→BS \to BS→B become S→0S \to 0S→0 , S→1S \to 1S→1 .

  57. [Exercises] Convert to Chomsky Normal Form: S→SA∣1A→0A1∣S∣0\begin{array}{rcl}S & \to & SA \mid 1 \\ A & \to & 0A1 \mid S \mid 0\end{array}SA​→→​SA∣10A1∣S∣0​

    SSS is on a right-hand side, so a new start variable S0S_0S0​ is needed: S0→SA∣1S→SA∣1A→CB∣SA∣1∣0B→ADC→0D→1\begin{array}{rcl}S_0 & \to & SA \mid 1 \\ S & \to & SA \mid 1 \\ A & \to & CB \mid SA \mid 1 \mid 0 \\ B & \to & AD \\ C & \to & 0 \\ D & \to & 1\end{array}S0​SABCD​→→→→→→​SA∣1SA∣1CB∣SA∣1∣0AD01​ S0→SS_0 \to SS0​→S and A→SA \to SA→S are unit productions, replaced by SA∣1SA \mid 1SA∣1 . A→0A1A \to 0A1A→0A1 becomes CADCADCAD , then CBCBCB with B→ADB \to ADB→AD .

  58. [Exercises] Convert to Chomsky Normal Form: S→CaCC→aDa∣εD→C∣bb\begin{array}{rcl}S & \to & CaC \\ C & \to & aDa \mid \varepsilon \\ D & \to & C \mid bb\end{array}SCD​→→→​CaCaDa∣εC∣bb​

    CCC , DDD nullable; terminals A→aA \to aA→a , B→bB \to bB→b : S→CE∣AC∣CA∣aC→AF∣AAD→AF∣AA∣BBE→ACF→DAA→aB→b\begin{array}{rcl}S & \to & CE \mid AC \mid CA \mid a \\ C & \to & AF \mid AA \\ D & \to & AF \mid AA \mid BB \\ E & \to & AC \\ F & \to & DA \\ A & \to & a \\ B & \to & b\end{array}SCDEFAB​→→→→→→→​CE∣AC∣CA∣aAF∣AAAF∣AA∣BBACDAab​ After the ε\varepsilonε -step and unit step: S→CaC∣aC∣Ca∣aS \to CaC \mid aC \mid Ca \mid aS→CaC∣aC∣Ca∣a , C→aDa∣aaC \to aDa \mid aaC→aDa∣aa , D→aDa∣aa∣bbD \to aDa \m…

  59. [Exercises] Convert to Chomsky Normal Form: S→aaa∣DCC→CD∣εD→bb∣bbb∣ε\begin{array}{rcl}S & \to & aaa \mid DC \\ C & \to & CD \mid \varepsilon \\ D & \to & bb \mid bbb \mid \varepsilon\end{array}SCD​→→→​aaa∣DCCD∣εbb∣bbb∣ε​

    All variables are nullable, so S→εS \to \varepsilonS→ε stays: S→AE∣DC∣CD∣BB∣BF∣εC→CD∣BB∣BFD→BB∣BFE→AAF→BBA→aB→b\begin{array}{rcl}S & \to & AE \mid DC \mid CD \mid BB \mid BF \mid \varepsilon \\ C & \to & CD \mid BB \mid BF \\ D & \to & BB \mid BF \\ E & \to & AA \\ F & \to & BB \\ A & \to & a \\ B & \to & b\end{array}SCDEFAB​→→→→→→→​AE∣DC∣CD∣BB∣BF∣εCD∣BB∣BFBB∣BFAABBab​ After the ε\varepsilonε -step and unit step: S→aaa∣DC∣CD∣bb∣bbb∣εS \to aaa \mid DC \mid CD \mid bb \mid bbb \mid \varepsilonS→a…

  60. [Exercises] Find a context-free grammar over {0,1}\{0, 1\}{0,1} for the strings of odd length that start and end with 111 , then convert it to Chomsky Normal Form.

    S→1A1∣1, A→BAB∣B, B→0∣1\boldsymbol{S \to 1A1 \mid 1, \ A \to BAB \mid B, \ B \to 0 \mid 1}S→1A1∣1, A→BAB∣B, B→0∣1 AAA generates exactly the strings of odd length, so 1A11A11A1 has odd length too.In CNF: S→CW∣1S \to CW \mid 1S→CW∣1 , C→WAC \to WAC→WA , W→1W \to 1W→1 , A→BD∣0∣1A \to BD \mid 0 \mid 1A→BD∣0∣1 , D→ABD \to ABD→AB , B→0∣1B \to 0 \mid 1B→0∣1 .