Exercícios resolvidos sobre GLC na forma normal de Chomsky do 1º/2013

Prévia do material em texto

Autoˆmatos e Computabilidade – Teste 3
Construa uma GLC, na forma normal de Chomsky, que gere a linguagem
L = {anbmcmd2n|n ≥ 0,m > 0}.
Resposta: A linguagem e´ gerada pela GLC
S → aSdd | A
A → bAc | bc
Uma GLC equivalente na forma de normal Chomsky e´
S0 → XU1 | BU2
S → XU1 | BU2
U1 → SU3
U2 → AC
U3 → DD
A → BU2 | BC
X → a
B → b
C → c
D → d
Construa uma GLC, na forma normal de Chomsky, que gere a linguagem
L = {anbm| 0 ≤ n ≤ m ≤ 2n}.
Resposta: A linguagem e´ gerada pela GLC
S → aSb | aSbb | ε
Uma GLC equivalente na forma de normal Chomsky e´
S0 → AU1 | AU2 | AB | AU3 | ε
S → AU1 | AU2 | AB | AU3
U1 → SB
U2 → SU3
U3 → BB
A → a
B → b
Construa uma GLC, na forma normal de Chomsky, que gere a linguagem
L = {1n0m1m0p1p0n|m,n, p > 0}.
Resposta: A linguagem e´ gerada pela GLC
S → 1A0
A → 1A0 | B
B → CC
C → 0D1
D → 0D1 | ε
Uma GLC equivalente na forma de normal Chomsky e´
S0 → RT
A → RT | CC
B → CC
C → SU | RS
D → SU | RS
T → AS
U → DR
R → 1
S → 0
Considere a seguinte GLC
S → aSa | aBa
B → bB | b
1. Que linguagem gera?
2. Converta-a em uma GLC equivalente na forma de normal Chomsky.
Resposta: A grama´tica gera L = {anbman|n,m > 0}. Uma GLC equivalente na forma de
normal Chomsky e´
S0 → AR | AT
S → AR | AT
B → XB | b
R → SA
T → BA
X → b
A → a
Considere a seguinte GLC
S → abScB | ε
B → bB | b
1. Que linguagem gera?
2. Converta-a em uma GLC equivalente na forma de normal Chomsky.
Resposta: A grama´tica gera L = {(ab)n(cbm)n|n ≥ 0,m > 0}. Uma GLC equivalente na
forma de normal Chomsky e´
S0 → AU1 | AU4 | ε
S → AU1 | AU4
U1 → XU2
U2 → SU3
U3 → CB
U4 → XU3
B → XB | b
A → a
X → b
C → c
Considere a seguinte GLC amb´ıgua
S → Ab | aaB
A → a | Aa
B → b
1. A grama´tica gera uma cadeia com duas derivac¸o˜es mais a` esquerda diferentes. Qual e´ essa
cadeia?
Resposta: A cadeia aab possui as seguintes derivac¸o˜es mais a` esquerda:
S ⇒ aaB ⇒ aab
S ⇒ AB ⇒ AaB ⇒ aaB ⇒ aab
2. Construa uma GLC equivalente na˜o-amb´ıgua na forma normal de Chomsky. Dica: pense
qual a linguagem gerada pela GLC.
Resposta: A linguagem gerada pela GLC e´ aa∗b. Uma GLC na˜o amb´ıgua equivalente e´
S → Ab
A → a | Aa
que, convertida na forma de normal Chomsky, resulta em
S → AB
A → a | AX
X → a
B → b