Gramaticas regulares
2476 palavras
10 páginas
Trabalho de investigação: Gramáticas RegularesÍndice
Introdução .................................................................................................................................. 1
Gramáticas Regulares ................................................................................................................ 3
Teorema: .................................................................................................................................... 5
Gramática Regular: .................................................................................................................... 7
Teorema: .................................................................................. Error! Bookmark not defined.
Teorema: Construção de um AF a partir de uma Gramática Regular: .................................... 8
Exemplo: Construção de um AF a partir de uma Gramática Regular..................................... 9
Exemplo: Construção de uma Gramática Regular a Partir de um AFD ................................... 9
Tradução dos Formalismos das Linguagens Regulares: .......... Error! Bookmark not defined.
Poder Expressivo ..................................................................... Error! Bookmark not defined.
Regras regulares a esquerda e a direita .................................... Error! Bookmark not defined.
Teoria de autômatos: linguagem formal e gramática formal ... Error! Bookmark not defined.
Bibliografia .............................................................................................................................. 12
Linguagens Formais e Autómatos
Page 0
Trabalho de investigação: Gramáticas Regulares
1. Introdução
Uma linguagem é regular se for aceite por um DFA ou um NFA. Poderemos assim representar uma linguagem pelo seu autómato. Se o autómato tiver um elevado número de estados, não é possível, por simples inspecção visual, ver qual a sua linguagem. Interessa por isso uma forma mais