Av1_-_Linguagens_Formais_1

Prévia do material em texto

AV1 – Trabalho Acadêmico
Disciplina: Linguagens Formais 
Professor: Sérgio Assunção Monteiro
1. A atividade deve ser entregue individualmente no local apropriado do AVA
2. As resoluções da atividade devem ser digitadas, ou escritas em letra legível
3. A atividade deve conter:
1. Nome da disciplina 
2. Código da Turma
3. Nome e matrícula do aluno
4. A data de entrega é até 08/10/2021.
5. Esta atividade vale 6,0 pontos na composição da nota da AV1.
6. Todas as respostas devem ser justificadas.
7. O arquivo deve estar no formato PDF
Questão 1 (3,0 pontos)
Seja o alfabeto Σ= {0, 1} e uma expressão regular cuja linguagem pode ser representada por (Σ Σ Σ)*. Faça:
(a) Apresente a respectiva expressão regular 
(b) Obtenha o respectivo AFN com transições vazias
(c) Obtenha o respectivo AFN sem transições vazias
(d) Obtenha o respectivo AFD eliminando transições que não reconhecem palavras.
(e) Faça o processamento da palavra 011001 pelo AFD
(f) Faça o processamento da palavra ε (cadeia vazia)
Questão 2: (3,0 pontos)
Observe a gramática livre de contexto G = ({S, A, B, C}, {a, b, ε}, S, P), onde o conjunto P é dado por:
S → AB | SCBA 
A → aAB | C 
B → bB | b 
C → cCA | ε
Faça:
(a) Obtenha a forma Normal de Chomsky.
(b) A GLC na forma normal de Chomsky é uma Gramática Regular? Em caso positivo, apresente uma justificativa. Caso negativo, justifique sua resposta.
Observação: pode usar o python e as bibliotecas vistas na aula, mas é necessário colocar o código no final do trabalho.