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ã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.
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.
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
Á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:
Dada gramática G seguinte, use a notação de conjunto para definir a linguagem gerada pela mesma.
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).
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: