Exercicios resolvidos de teoria dos automatos e linguagens formais

Exercicios resolvidos de teoria dos automatos e linguagens formais

(Parte 1 de 2)

Universidade Estadual do Ceará Centro de Ciências e Tecnologia Curso de Ciência da Computação Disciplina: Teoria dos Autômatos e Linguagens Formais Professor: Edson Pessoa Semestre Acadêmico 2009.2

Resolução do 2a NTI

Aluno: Neuton de Oliveira Braga Jr E-mail: neutonjr2008@gmail.com

Fortaleza - CE 17 de janeiro de 2010

Questões e Respostas

Questão 1 Seja G a gramática:

S → ASB | λ (I) A → aAb | λ (I) B → bBa | ba (I) a) Dê a derivação mais à esquerda de aabbba.

Resposta:

S ⇒ ASB por (I) ⇒ aAbSB por (I)

⇒ aaAbbSB por (I)

⇒ aabbSB por (I)

⇒ aabbB por (I)

⇒ aabbba por (I) b) Dê a derivação mais à direita de abaabbbabbaa.

Resposta:

S ⇒ ASB por (I) ⇒ ASbBa por (I)

⇒ ASbbaa por (I)

⇒ AASBbbaa por (I)

⇒ AASbabbaa por (I)

⇒ AAbabbaa por (I)

⇒ AaAbbabbaa por (I)

⇒ AaaAbbbabbaa por (I)

⇒ Aaabbbabbaa por (I)

⇒ aAbaabbbabbaa por (I)

⇒ abaabbbabbaa por (I) c) Construa as árvores de derivação dos itens a e b. 3

Resposta:

Árvore de derivação Ordem dos Filhos

S ASB aAbba aaAbbba aabbba

S ASB aAbASBbBa abaAbbabbaa abaaAbbbabbaa abaabbbabbaa

d) Use a notação de conjunto para definir L(G). Resposta:

Questão 2

Dada gramática G seguinte, use a notação de conjunto para definir a linguagem gerada pela mesma.

Resposta:

Questão 3

Resposta:

Questão 4 Seja G a gramática:

S → aSaa | B (I) B → bbBdd | C (I) C → bd (I) a) Qual a linguagem gerada por G?

b) Prove que L(G) é o conjunto do item a).

Resposta: Seja o conjunto de palavras X = {amb2n+1d2n+1a2m | m,n > 0} sobre o alfabeto Σ = {a,b,d}. Para provar que L(G) = X, inicialmente provaremos que X ⊆ L(G) e, depois, L(G) ⊆ X: P1) X ⊆ L(G): Essa prova é feita ao se mostrar que toda palavra w ∈ X é derivável de G. A idéia é se encontrar um padrão de derivação que se aplique a qualquer palavra w ∈ X.

Assim, se w ∈ X então w tem a forma amb2n+1d2n+1a2m , para m,n ≥ 0, e pode ser obtida usando-se as seguintes derivações:

P2) L(G) ⊆ X: Essa prova é feita ao se mostrar que toda palavra w derivável de G pertence a X. Para isso, caracterizaremos uma palavra u ∈ X por meio de algumas relações, e, por conseguinte, mostraremos que toda sentença obtida de G também satisfaz essas relações.

Seja nu(c) o número de vezes que o símbolo c aparece numa palavra u. Podemos caracterizar as palavras u ∈ X por meio de algumas relações. São elas:

1. Quanto ao número de símbolos da palavra u:

2. Quanto à quantidade mínima de cada símbolo na palavra u. Duas situações:

3. Quanto à precedência, as ocorrências de a's precedem b's, que precedem d's e que, por sua vez, precedem uma quantidade de a's correspondente ao dobro da quantidade do mesmo símbolo no início da palavra.

E, também podemos caracterizar, quanto à quantidade de cada símbolo e quanto à precedência dos símbolos, uma forma sentencial qualquer, após aplicar cada uma das regras de derivação (tabela abaixo). Para tanto, considere nu(c) o número de vezes que o símbolo c aparece explicitamente na forma sentencial u antes da derivação, nu(c,C) o número de vezes que o símbolo c aparece por meio da variável C na forma sentencial u antes da derivação, e, n′u(c) o número de vezes que o símbolo c aparece na forma sentencial u depois de aplicada a regra de derivação.

dois a's no final

Diante disso, provaremos que as relações 1, 2 e 3 se mantém para as sentenças obtidas por derivações a partir de S. Essa prova se dará por indução sobre o número de derivações partindo de S, sendo na análise de uma forma sentencial específica sempre será considerada a sentença mais próxima a ela obtida pela derivação das variáveis da forma sentencial, um número mínimo de vezes, para obter apenas símbolos terminais. Assim, temos:

Desse modo, a indução é feita da seguinte forma: Base: Para uma única derivação, temos dois casos:

Assim:

Relações Regras S → aSaa S → B

(Parte 1 de 2)

Comentários