Homework 6 Automata & Grammars

1.

M1

a.

Σ→AA→0B→0C→1A→1BA→0AB→0AB→0BB→1CC→0CC→1A\Sigma\to A\\ A\to0\\ B\to0\\ C\to1\\ A\to 1B\\ A\to0A\\ B\to0A\\ B\to0B\\ B\to1C\\ C\to 0C\\ C\to 1A

b.

M2

a.

Σ→A∣C∣λA→0B∣1CC→0∣0AB→0∣0DD→1B∣1C\Sigma\to A|C|\lambda\\ A\to0B|1C\\ C\to 0|0A\\ B\to 0|0D\\ D\to 1B|1C

b.

c.

E(B)=0E(D)={0,010,01010,0101010,010101010,01010101010,0101010101010,010101010101010,01010101010101010,,010101010101010,...}E(A)=1E(C)∪0E(B)∪λ={λ,10,1010,101010,10101010,1010101010,101010101010,10101010101010,10101010101010,1010101010101010,...}E(D)=1E(B)∪1E(C)∪λE(C)=0E(A)E(B)=0E(D)=\{0,010,01010,0101010,010101010,01010101010,0101010101010,010101010101010,01010101010101010,,010101010101010,...\}\\ E(A)=1E(C)\cup0E(B)\cup\lambda=\{\lambda,10,1010,101010,10101010,1010101010,101010101010,10101010101010,10101010101010,1010101010101010,...\}\\ E(D)=1E(B)\cup1E(C)\cup\lambda\\ E(C)=0E(A)

2.

a.

A=1BB=0B∪1CC=0D∪1D∪λD=0E∪λE=0A∪1BA=1B\\ B=0B\cup1C\\ C=0D\cup1D\cup \lambda\\ D=0E\cup \lambda\\ E=0A\cup 1B\\

b.

Σ→A∣BA→1BB→0B∣1C∣1C→0D∣1D∣0∣1D→0EE→0A∣1B\Sigma\to A|B\\ A\to1B\\ B\to0B|1C|1\\ C\to0D|1D|0|1\\ D\to 0E\\ E\to 0A|1B

c.

3.a

3.b

4.a M4

Σ→SS→λ∣A∣B∣CA→0EE→1SB→0DD→0SC→1FF→1S\Sigma\to S\\ S\to \lambda|A|B|C\\ A\to 0E\\ E\to 1S\\ B\to 0D\\ D\to0S\\ C\to1F\\ F\to1S
Σ→SS→λE→A0A→SS→E1D→B0B→SS→D0F→C1C→SS→F1\Sigma\to S\\ S\to \lambda\\ E\to A0 \\ A\to S \\ S\to E1\\ D\to B0\\ B\to S\\ S\to D0\\ F\to C1\\ C\to S\\ S\to F1

4.b M4

4.a M5

Σ→SS→A∣BA→C∣D∣λC→abAD→bcAB→E∣F∣λE→acBF→dB\Sigma\to S\\ S\to A|B\\ A\to C|D|\lambda\\ C\to abA\\ D\to bcA\\ B\to E|F|\lambda\\ E\to acB\\ F\to dB
Σ→SS→A∣BA→C∣D∣λC→AabD→AbcB→E∣F∣λE→BacF→Bd\Sigma\to S\\ S\to A|B\\ A\to C|D|\lambda\\ C\to Aab\\ D\to Abc\\ B\to E|F|\lambda\\ E\to Bac\\ F\to Bd

4.b M5

  1. G1

5. G2