Linguagens Formais e Autômatos

José Fontebasso Neto · UniSantos

[[00 - Mapa da Disciplina]]

Conceitos básicos

[[01 - Introdução e Conceitos Básicos]]

• alfabeto V (finito)
• sentença w, |w|, ε
• V* e V+
• linguagem L ⊆ V*
• sintaxe × semântica

Matemática discreta

[[02 - Matemática Discreta]]

• produto cartesiano K × V
• função × relação
• R* e R+ (fechos)
• equivalência, classes, partição
• conjuntos enumeráveis

Gramáticas

[[03 - Gramáticas Regulares]]

• G = (Vn, Vt, S, P)
• derivação ⇒, ⇒*, ⇒+
• L(G) = {w ∈ Vt* | S ⇒* w}
• regular: A → aB | a
• regra vazia: S → ε (ou S')

Expressões regulares

[[03b - Expressões Regulares]]

• | concatenação *
• precedência: * > concat > |
• α+, α?, αⁿ
• identificador: L(L|D)*

Linguagens regulares

Mesma classe descrita por: AFD = AFND = Gramática regular = Expressão regular

Não regular: 0ⁿ1ⁿ (precisa de memória infinita)

Estudar

[[Glossário]] · [[Flashcards]] · [[Referências - Livros]]

AFD

[[04 - Autômatos Finitos Determinísticos]]

• M = (K, V, T, i, F)
• T: K × V → K (um destino)
• diagrama · tabela · algébrica
• T̂(q, ua) = T(T̂(q,u), a)
• aceita se T̂(i, w) ∈ F

AFND

[[05 - Autômatos Finitos Não Determinísticos]]

• T: K × V → 2^K (conjunto)
• várias cópias em paralelo
• aceita se ALGUM caminho termina em F
• facilita, não aumenta o poder

AFD ≡ AFND

[[06 - Equivalência AFD e AFND]]

• construção de subconjuntos
• estado do AFD = conjunto de estados
• T' = união das transições
• final se contém algum final

AF ≡ GR

[[07 - Equivalência AF e GR]]

• estado ↔ não terminal
• T(B,a)=C ↔ B → aC
• chegar em final ↔ B → a
• GR → AF usa estado novo Z

Hierarquia de Chomsky