CE-EDA4 Autômatos Determinísticos e Não-Determinísticos

Front

O que são autômatos?

Back

Autômatos são modelos matemáticos usados para reconhecer linguagens formais e são a base teórica para a construção de compiladores, interpretadores e processadores de linguagens.

Front

Quais são os tipos de autômatos abordados neste material?

Back

Autômatos Finitos Determinísticos (AFD) e Autômatos Finitos Não-Determinísticos (AFN).

Front

O que é um Autômato Finito Determinístico (AFD)?

Back

Um AFD é uma máquina de estados finitos onde, para cada estado e símbolo de entrada, há exatamente um estado seguinte.

Front

Quais são os componentes de um AFD?

Back

Um AFD é definido por uma 5-tupla: (Q, Σ, δ, q0, F), onde Q é o conjunto finito de estados, Σ é o alfabeto de entrada, δ é a função de transição, q0 é o estado inicial, e F é o conjunto de estados finais.

Front

Dê um exemplo de AFD.

Back

Um AFD que reconhece strings binárias com número par de '1's, com estados Q={q0, q1}, alfabeto Σ={0,1}, e transições δ(q0,0)=q0, δ(q0,1)=q1, δ(q1,0)=q1, δ(q1,1)=q0, com estado final F={q0}.

Front

Quais são as características de um AFD?

Back

Determinístico: A cada entrada, apenas um caminho possível. Reconhecimento: Aceita uma string se terminar em um estado final.

Front

O que é um Autômato Finito Não-Determinístico (AFN)?

Back

Um AFN permite zero, uma ou múltiplas transições para o mesmo símbolo de entrada e pode incluir transições vazias (ε-transições).

Front

Quais são os componentes de um AFN?

Back

Um AFN é definido por (Q, Σ, δ, q0, F), onde δ é a função de transição δ:Q×(Σ∪{ε})→P(Q).

Front

Dê um exemplo de AFN.

Back

Um AFN que reconhece strings terminadas com '01', com estados Q={q0, q1, q2}, alfabeto Σ={0,1}, e transições δ(q0,0)={q0,q1}, δ(q0,1)={q0}, δ(q1,1)={q2}, com estado final F={q2}.

Front

Quais são as características de um AFN?

Back

Não-determinístico: Pode ter múltiplos caminhos para uma entrada. Aceitação: Basta um caminho levar a um estado final.