AULA 8: GRAMATICAS LIVRES DE CONTEXTO
=====================================

Motivacao:  especificar a sintaxe de uma linguagem

<comando-if> -> IF <expr-bool> THEN <comando> 
<comando-if> -> IF <expr-bool> THEN <comando> ELSE <comando>
<comando>    -> <comando-if> 
<comando>    -> <atribuicao>
<atribuicao> -> <var> := <expr>
<expr>       -> <expr-bool> | <expr-inteira>
<expr-bool>  -> <expr> = <expr>
<expr-bool>  -> <expr> < <expr>
<expr-bool>  -> not <expr-bool>
<expr-bool>  -> <expr-bool> AND <expr-bool>
<expr-bool>  -> TRUE
<expr-bool>  -> FALSE
<expr-inteira>  -> <var> | <inteiro>
<var>        -> A | B | C | D | E
<inteiro>    -> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10

- Exemplo de palavra:  IF A = 10 AND B < 100 THEN B := C ELSE B := 7
- Mostrar derivacao a partir de <comando>

- diferenca entre sintaxe e semantica:  
  O seguinte comando nao faz sentido:
  IF FALSE THEN A := 10 

DEF:  Uma gramatica livre de contexto e' uma quadrupla (V, Sigma, P, S), onde
  V e' um conjunto de simbolos nao terminais ou variaveis
  Sigma e' um conjunto de simbolos terminais (o alfabeto) 
        V intersecao Sigma = emptyset
  P e' um conjunto de producoes.  P [  V x (V U Sigma)*.  Uma producao ou
       regra (A, w) e' normalmente escrita  A -> w
  S \in V e' o simbolo iniciall


Uma palavra w e' DERIVAVEL de v na gramatica G se existe uma sequencia
de aplicaoes de regras que transforma v em w, ou seja,
   v => v1 => v2 => ... => w

  n
 ===> : derivacao em n passos
  *
 ===> : derivacao em 0 ou mais passos
  + 
 ===> : derivacao em 1 ou mais passos

DEF: seja G= (V, Sigma, P, S) uma gram. livre de contexto:    *
  - um string w em (V U Sigma)* e' uma FORMA SENTENCIAL de S ===> w
  - um string w em Sigma* e' uma palavra de G se existe uma derivacao
    S ===> w em G
  - a linguagem de G, representada por L(G) e' o conjunto
    { w em Sigma* | S ==> w}

Exemplo de derivacao:

L = { w em {0,1}* | w possui numero par de 0's}

definicao recursiva de L:
 a) epsilon em L
 b) se w em L entao w00, 00w, 0w0, w1, e 1w tambem estao em L

G1:  S -> epsilon | S00 | 00S | 0S0 | S1 | 1S

derivacao de 0011010
  S => 0S0 => 0S10 => 00S010 => 001S010 => 0011S010 => 0011010

Outra gramatica que gera a mesma linguagem:

G2:  S -> epsilon | AA | 1S
     A -> AAA | 1A | A1 | 0

  S => AA => AAAA => 0AAA => 00AA => 001AA => 0011AA => 00110A =>
       001101A => 0011010
                          
Outra gramatica para a mesma linguagem (que usa ideia de estados):

G3 :  S -> 1S | 0B | epsilon
      B -> 1B | 0S


DEF: Seja G = (V, Sigma, P, S) uma gramatica e S==>w uma derivacao.
A arvore de derivacao, AD de S ===> w  e' uma arvore ordenada construida
iterativamente como:            *
  a) inicializa a arvore com a raiz S
  b) se A -> x1 x2... xn e' aplicado a forma sentencial uAv entao 
     x1 x2 ... xn sao filhos de A na arvore
  c) se A -> epsilon e' a regra aplicada ao string uAv entao \epsilon e' o
unico filho de A na arvore

  Exemplo das arvores para as derivacoes acima.

EXEMPLOS DE LINGUAGENS E AS GRAMATICAS QUE A GERAM:
1) que linguagem e' gerada pelas seguintes gramaticas?
      -  S -> aSa | aBa
         B -> bB | b

         { a^n b^m a^n | n, m >=1 }

      - S -> aSdd | A
        A -> bAc | bc

         { a^n b^m c^m d^{2n} | n>= 0,  m >= 1 }

      - S -> aSb | aSbb | epsilon

         { a^n b^m | 0 <= n <= m <= 2n }

1)    - {w in {a,b}* | w e' uma palindrome}
      - {a^i b^j | i = j}
      - {a^i b^j | i > j}
      - que geram palavras com o mesmo numero de a's e b's
          S -> epsilon | aB | bA
          A -> a | aS | bAA
          B -> b | bS | aBB

GRAMATICAS REGULARES OU LINEARES A DIREITA:
==========================================

Uma gramatica livre de contexto G=(V, Sigma, P, S) e' regular se todas
as producoes em P sao da forma:
  A -> epsilon
  A -> a, a \in Sigma
  A -> aB, a \in Sigma, B \in V

Uma linguagem e' regular se pode ser gerada por uma gramatica regular.

Ex: a linguagem denotada pela expr. regular a^+ b^* pode ser gerada pela
seguinte gramatica:
 
  S -> aS | aB
  B -> bB | epsilon

Ex: (a+b)* c
  S -> aS | bS | c


           
2) EQUIVALENCIA GRAMATICA REGULAR / AUTOMATO FINITO
---------------------------------------------------
Relembrar a definicao de gramatica regular:
  todas as producoes na forma A -> epsilon | a | aB

Exemplo:  G: S -> aS | aA  automato M(G):
             A -> bA | b

- Gramatica --> Automato:
  Seja G=(V,Sigma,P,S) uma gramatica regular.  Defina o NFA
M=( Q, Sigma, delta, S, F), onde
  - Q = V uniao {Z}, onde Z nao pertence a V, se P contem uma prod. A->a
        V            caso contrario
  - delta(A,a) = B se A->aB pertence a P
    delta(A,a) = Z se A->a  pertence a P
  - F = {A | A -> epsilon pertence a P} uniao {Z} se Z pertence a Q
        {A | A -> epsilon pertence a P}           caso contrario
Entao L(M) = L(G).

- Automato ---> Gramatica Regular
  - Utilizar o mesmo algoritmo para a transformacao de gramatica para
automato de forma reversa.  
  - Se o estado A e' um estado final, entao a gramatica deve conter a
producao A->epsilon.

Exemplo: