Folha de estudo

Expressões regulares:
[0-9]+
[1]*
[1]?
[1]{2,5}
[1] {2,}
[1] {4}
[^A-Z\n]
.
^r
r$

::=
|
tem uma ou mais ocorrências pode ter varias ocorrências ou não ter nenhuma zero ou uma vez repetido no mínimo duas e máximo cinco vezes repetido pelo menos duas vezes repetido exatamente quatro vezes qualquer carácter excepto de A-Z ou mudança de linha qualquer carácter excepto mudança de linha o carácter “r” apenas se no inicio da linha o carácter “r” apenas se no final da linha

Definir formalmente a gramatica:

Verificar se uma expressão regular representa uma gramatica
(usando o exemplo de cima):
Ex. Regular: (x+ yz* x+)

definido como alternativa regra

[]
{}
vezes
““

parte opcional repetir 0 ou + terminal Ex:
::= if then [else ] end if ::=(|_){(||_)}
::= a|A|b|…|z|Z
::= 0|1|2|3|…|8|9
Autómato finito para gramatica:

logo, verdadeira
Hierarquia de Chomsky:

Exemplos:

Autómato finito:

AFN se com o mesmo valor puder transitar para mais que um estado
AFD se com um valor apenas transitar para um único estado

Representação formal de um autómato:
A({S0, S1, S2}, {a,b}, S0, {S2}, δ)
Exemplo de minimização:

Tipo 0
 Gramáticas livres ou sem restrições.  Forma: α → β
 tanto α como β são sequências arbitrárias de símbolos terminais e não terminais.  O lado esquerdo da produção não pode ser vazio.
Ex:
S→aSBC|abC
CB→BC
bB→bb bC→bc cC→cc

Tipo 1
 Gramáticas dependentes do contexto.  Forma: αAβ → αγβ
 α,β e γ são sequências arbitrárias de símbolos terminais e não terminais, sendo que γ não é nulo e A é um não terminal singular.
 Estas gramáticas têm que respeitar a condição |αAβ| ≤
|αγβ|, existindo uma única exceção a esta regra, a produção inicial pode ser do tipo S→ ε se o S não existir do lado direito
(para permitir a palavra vazia).
Ex:
S→aSBC|abC
CB→XB
XB→XC
XC→BC
bB→bb bC→bc cC→cc

Tipo 2
 Gramáticas independentes do contexto.
 Forma: A→ α
 α é