Context-Free Languages/Grammars

Context-Free Languages/Grammars

Construct one context-free grammar each that generate exactly one of the following languages:

• G₁(L₁={0^a1^b0^c | 0≤a<b ∧ c=b-a}) = G(N=?, E=?, S=?, P=?)

N =  { S, A, B }

E = { 0, 1 }

S à AB

A à  ∑ | 0A1

B à 1B0 | 10

 

• G₂(L₂={0^c1^b0^a | 0≤a<b ∧ c>b-a}) = G(N=?, E=?, S=?, P=?)

N = {S, A, B}

E = { 0, 1 }

S à ABC

A à 0A | ∑

B à 1B0 | 10

C à ∑ | 0C1

 

• G₃(L₃={0(1+0)^*1}) = G(N=?, E=?, S=?, P=?)

N =  { S, A, B, C }

E = { 0, 1 }

S à 0A1

A à ∑ | 10A | 1A | 0A | 01A

 

 

• G₄(L₄={0(1⁺+0⁺)^*1}) = G(N=?, E=?, S=?, P=?)

N =  { S, A, B, C }

E = { 0, 1 }

S à 0A1

A à ∑ | BC | B0 | C1 |CB

B à 1 | 1B

C à 0 | 0C

 

• G₅(L₅={0⁺+(1⁺+0⁺)^*1}) = G(N=?, E=?, S=?, P=?)

N =  { S, A, B, C, D }

E = { 0, 1 }

S à AB1

A à 0 | A0

B à ∑ | CD | C0 | D1 | DC

C à 1 | 1C

D à 0 | 0D