******************************
********** TEO - P1 **********
******************************

Data     : 03/09/2003 a 12/09/2003
Versão   : 04/07/2007
Professor: Francisco Aurélio de Souza Grossi
Autor    : Leandro Salvador ( leandrosalvador.com.br )

* Prova

1) Dada a gramática regular G1 = ({S,A}, {a,b}, {S --> aA, A --> bS, S --> T(lambda)}, S)
a) Que tipo de gramática regular é L(G1)?
    - GLUD
b) Descreva formalmente, usando conjuntos, a linguagem L(G1)
    - L(G1) = {(ab)^n : n >= 0}
c) Mostre a derivação de uma sentença qualquer de comprimento 4 de L(G1)
    - S ==> aA ==> abS ==> abaA ==> ababS ==> abab
d) Escreva uma expressão regular que gera a linguagem L(G1)
    - ER = (ab)*
e) Desenhe o diagrama de estados de um AFD que reconhece a linguagem L(G1)

    -->((1))-----a---->(2)
         | ^-----b-----´|
         |              |
         '--b-->(3)<-a--'
                |_^
                a,b

2) Dada a gramática regular G2 = ({S,A}, {0,1}, {S --> 1S|1A|0A, A --> 0}, S)
a) Descreva formalmente, usando conjuntos, a linguagem L(G2)
    - L(G2) = {1^n 0 : n > 0} U {1^m 00 : m >= 0}
b) Escreva uma expressão regular que gera a linguagem L(G2)
    - ER = 1 + 0 | 1*00

3) Dada a linguagem L(G3) = {a^n bc : n >= 0}
a) Escreva uma gramática regular G3 que gera esta linguagem
    - G3 = ({S}, {a,b,c}, {S --> aS, S --> bc}, S)
b) Qual é o tipo de sua gramática G3?
    - GLD
    - 0BS: Não é unitário por isso: S --> bc
c) Outro exemplo
    - G3 = ({S,A,B}, {a,b,c}, {S --> as, S --> A, A --> bB, B --> c}, S)
    - GLUD

4) Dado o AFD M abaixo, cujo alfabeto é E = {a,b}

                       b               a
                      |¯¯v            |¯¯v
    -->(q0)-----a---->(q1)-----a---->((q2))
        |                ^-----b-----´
        |
        |
        '-------b---->(q3)
                      |__^
                       a,b

a) Descreva em português a linguagem L(M) aceita por M
    - Aceita sentenças que comecem e terminem com a
b) Descreva formalmente, usando conjuntos, a linguagem L(M) aceita
    - L(M) = {awa : w pertence E*}
c) Escreva uma expressão regular que gera esta linguagem L(M)
    - ER = a(a|b)*a

----------//----------