Recursively Enumerable Languages/Unrestricted Grammars

Recursively Enumerable Languages/Unrestricted Grammars 

Construct one unrestricted grammar each that generates exactly one of the following languages:

• G₁(L₁={aⁿbⁿ | 1≤n})        N = {S, A, B}         E = {a, b}

S à aAb

A à aAB

B à aB

Bb à bb

• G₂(L₂={aⁿbⁿcⁿ | 1≤n})       N = {S, A, B, C}        E = {a, b, c}

S à aSBC

CB à BC

aB à ab

bB à bb

bC à bc

cC à cc

• G₃(L₃={aⁿbⁿcⁿdⁿ | 1≤n})       N = {S, A, B, C, T}      E = {0, 1, 2}

 S à ABCDS 

S à TD 

DA à AD

DB à BD 

DC à CD 

CB à BC 

DTD à TDd 

TD à TC 

CTC à TCc 

TC à TB 

BTB à TBb 

TB à TA 

ATA à TAa 

TA à ∑

 

• G₄(L₄={0ⁱ1^j | 0<i<j})          N = {S, A, B, T}         E = {0, 1}

S à ABS

S à TB

BA à AB

BTB à TB1

TB à TA

ATA à TA0

TA à ∑

• G₅(L₅={0ⁱ1^j2^k | 0<i<j<k})      N = {S, A, B, C, T}     E = {0, 1, 2}

S à ABCS

S à TC

CA à AC

BA à AB

CB à BC

CTC à TC2

TC à TB

BTB à TB1

TB à TA

ATA à TA0

TA à ∑