Lfa linguagens formais e automotas

LFA - 3ª Lista Exercícios -Linguagens Livres Contexto – Data de entrega: 07/11/11

1- Verificar, usando o LEMA DO BOMBEAMENTO, se as linguagens abaixo são L.C.

a) Linguagem onde tenho um ‘a’ à esquerda e ‘b’s à direita

b) { ai bj | j = i }

c) { ai bj | j = 2i }

d) { ai bj | j ≠ i}

e) { ai bi ci | i > 0}

2 - Converta a seguinte gramática à Forma Normal de Chomsky:

S ( 00A | B | 1

A ( 1AA | 2

B ( 0

3 - Dê um APN de um estado que aceite a linguagem { wewR | w ( (d, f)* }

4 - Dê um APN (autômato de pilha) que aceite a linguagem { wwR | w ( (0, 1)* }

6 - Considere a gramática

G = ({0,1}, {S}, S, {S ( 0S1 | 01})

Escreva o APN que processa tal linguagem.

7 – Dê um APN que aceite a linguagem dos parênteses casados pelo estado final.

8 - Considere a seguinte linguagem livre de contexto L = {0n1n / n>=1}. Escreva um APN M que processe essa linguagem. Verifique como M age com as entradas 01 e 011.

9 - Seja o seguinte conjunto de produções da gramática livre de contexto G:

S → aaZcc

Z → aZc

Z → b

a) Qual é a linguagem que esta gramática gera?

b) L(G) é regular?

Observe agora o seguinte conjunto de produções da gramática linear à direita G’:

S → aA

A→ aB

B → aB / bC

C →cC / cD

D →c

c) Qual é a relação entre G e G’? São equivalentes? Por que?

d) Escreva o autômato de pilha que processa L(G).

10 - Escreva a gramática para a linguagem com cadeias que contenham um único a à esquerda e n b´s à direita: abn, n>0. Qual o tipo desta