Re: Gramáticas

[Leonidas O Brandao <leo@ime.usp.br>]

Olá

On Wed, 25 Jun 2003, Reginaldo do Prado wrote:

> Olá pessoal.
> 
> Surgiu uma dúvida sobre o ex. 06_02
> 
> "... Usando a gramática S -> aA | bB | c;  A -> aS | bS | a ;  B -> aS |
> bS | b. "
> 
> Devo assumir que o estado inicial é S ?

É isso mesmo.

> Se for,  não consegui encontrar a combinação de transições que
> justifica o fato de a cadeia " aabc " pertencer a esta linguagem, embora o
> tenha feito para " aac " e " bbc ".
> Se existe tal combinação qual é?

Tem razão, eu digitei errado, onde está escrito "aabc", leia-se
"aabb"! Para este a sequência de produções é:

  entrada: aabb
  S  -> aA  -> aaS  -> aabB  -> aabb
    (1)    (4)     (2)      (9)

(1) S -> aA
(2) S -> bB
(3) S -> c
(4) A -> aS
(5) A -> bS
(6) A -> a
(7) B -> aS
(8) B -> bS
(9) B -> b

> Muito obrigado,
> 
> Reginaldo.

Obrigado pela correção, já troquei a versão da lista de exercício 2 da
página de MAC323.

Bons estudos!
Leônidas

 --------------------------------------------------------------------------
 Leônidas de Oliveira Brandão  -  Computer Science Dep. of IME-USP (Brazil)
 leo@ime.usp.br - http://www.ime.usp.br/~leo - +55 (011) 3091 [6298 | 6135] 
 Interessado em Matemática?  Visite o "iMatica":   http://www.matematica.br