Baixe Exercicios resolvidos de teoria dos automatos e linguagens formais e outras Exercícios em PDF para Informática, somente na Docsity! 1 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 2 5 Questão 4 Seja G a gramática: S → aSaa | B (I) B → bbBdd | C (II) C → bd (III) a) Qual a linguagem gerada por G? Resposta: L(G) = {amb2n+1d2n+1a2m | m,n ≥ 0} 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: S ⇒ (a)mS(aa)m por (I) aplicada 'm' vezes, sendo (m ≥ 0) ⇒ (a)mB(aa)m por (I) ⇒ (a)m(bb)nB(dd)n(aa)m por (II) aplicada 'n' vezes, sendo (n ≥ 0) ⇒ (a)m(bb)nC(dd)n(aa)m por (II) ⇒ (a)m(bb)nbd(dd)n(aa)m por (III) ⇒ amb2n+1d2n+1a2m 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: nu(a) = 3m, com m ≥ 0. nu(b) = nu(d) = 2n+ 1, com n ≥ 0, ou seja, o número de b's e d's é ímpar. 2. Quanto à quantidade mínima de cada símbolo na palavra u. Duas situações: Quando a ocorre: nu(a) ≥ 3 e nu(b) = nu(d) ≥ 1. Quando a não ocorre: nu(b) = nu(d) ≥ 1. 6 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 à pre- cedê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. Regra n′u(a) n ′ u(b) n ′ u(d) Precedência S → aSaa nu(a) + nu(a, S) + 3 nu(b) + nu(b, S) nu(d) + nu(d, S) A cada um a colocado no início S, é colocado dois a's no nal S → B nu(a) + nu(a, B) nu(b) + nu(b, B) nu(d) + nu(d, B) Mesma precedência da variável B B → bbBdd nu(a) + nu(a, B) nu(b) + nu(b, B) + 2 nu(d) + nu(d, B) + 2 Os b's precedem o B, que precede os d's B → C nu(a) + nu(a, C) nu(b) + nu(b, C) nu(d) + nu(d, C) Mesma precedência da variável C C → bd nu(a) nu(b) + 1 nu(d) + 1 b precede d 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íca 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: Variável Sentença mais próxima n′u(a) n ′ u(b) n ′ u(d) C C ⇒ bd 0 1 1 B B ⇒ C ⇒ bd 0 1 1 S S ⇒ B ⇒ C ⇒ bd 0 1 1 Desse modo, a indução é feita da seguinte forma: Base: Para uma única derivação, temos dois casos: Regra n′u(a) n ′ u(b) n ′ u(d) Sentença mais próxima S → aSaa 0 + 0 + 3 = 3 0 + 1 = 1 0 + 1 = 1 abdaa S → B 0 + 0 = 0 0 + 1 = 1 0 + 1 = 1 bd Assim: Relações Regras S → aSaa S → B u = abdaa u = bd 1 nu(a) = 3 = 3 ∗ 1 nu(a) = 0 = 3 ∗ 0 nu(b) = nu(d) = 1 = 2 ∗ 0 + 1 nu(b) = nu(d) = 1 = 2 ∗ 0 + 1 2 nu(a) = 3 ≥ 3 nu(b) = nu(d) = 1 ≥ 1 nu(b) = nu(d) = 1 ≥ 1 3 a precede b que precede d que precede dois a's b precede d Logo, as relações 1, 2 e 3 são válidas para a base. 7 Hipótese: Suponha que as relações 1, 2 e 3 são válidas na análise para todas as formas sentenciais u obtidas da derivação em n > 0 passos. Assim, seja iu, ju e ku o número de vezes que as variáveis S, B e C, respectivamente, aparecem em u, então n′u(a), n ′ u(b) e n ′ u(d) são dados por: n′u(a) = nu(a) + iu.nu(a, S) + ju.nu(a,B) + ku.nu(a, C) = nu(a) = 3x, com x ≥ 0 n′u(b) = nu(b) + iu.nu(b, S) + ju.nu(b, B) + ku.nu(b, C) = nu(b) + iu + ju + ku = 2y + 1, com y ≥ 0 n′u(d) = nu(d) + iu.nu(d, S) + ju.nu(d,B) + ku.nu(d, C) = nu(d) + iu + ju + ku = 2y + 1, com y ≥ 0 Indução: Seja u e w formas sentenciais derivadas após, respectivamente, n e (n+1) passos: S n+1⇒ w S n⇒ u⇒ w Devemos provar que as relações 1, 2 e 3 se aplicam a w. Partindo da hipótese de indução, podemos encontrar a seguinte tabela com valores impor- tantes relacionados com a palavra w, especialmente n′w(a), n ′ w(b) e n ′ w(d): Regra nw(a) nw(b) nw(d) iw jw kw n′w(a) n ′ w(b) n ′ w(d) S → aSaa nu(a) + 3 nu(b) nu(d) iu ju ku n′u(a) + 3 n′u(b) n′u(d) S → B nu(a) nu(b) nu(d) iu − 1 ju + 1 ku n′u(a) n′u(b) n′u(d) B → bbBdd nu(a) nu(b) + 2 nu(d) + 2 iu ju ku n′u(a) n′u(b) + 2 n′u(d) + 2 B → C nu(a) nu(b) nu(d) iu ju − 1 ku + 1 n′u(a) n′u(b) n′u(d) C → bd nu(a) nu(b) + 1 nu(d) + 1 iu ju ku − 1 n′u(a) n′u(b) n′u(d) Com isso, percebe-se que todos os valores n′w(a), n ′ w(b) e n ′ w(d) encontrados satisfazem a relação 1. As relações 2 e 3 podem ser também facilmente vericadas. Logo, L(G) ⊆ X. Assim, por P1) e P2), temos que L(G) = X. Questão 5 Seja M o autômato nito determinístico abaixo: M δ a b > q0 q0 q1 q1 q2 q1 < q2 q2 q0 a) Dê o diagrama do estado de M. Resposta