Algebricamente, um Autômato Finito M pode ser definido como uma quíntupla:
M = (Q, Σ, δ, q0, F)
No caso de q0 ∈ F, pode-se concluir que esse Autômato Finito:
Na Teoria da Computação, um Autômato Finito Não-Determinístico (AFN) é uma máquina de estados finita, onde para cada par de estado e símbolo de entrada pode haver vários próximos estados possíveis. Essa característica o distingue do Autômato Finito Determinístico (AFD), onde o próximo estado possível é univocamente determinado. Autômatos Finitos Não-Determinísticos reconhecem exatamente o conjunto de Linguagens Regulares que são, dentre outras coisas, úteis para a realização da Análise Léxica e reconhecimento de padrões. Qual a Linguagem Regular reconhecida pelo Autômato Finito Não-Determinístico apresentado a seguir:
M = ({a, b}, {q0, q1, q2}, δ, q0, {q2})
As Expressões Regulares (ER) sobre um alfabeto Σ podem ser definidas recursivamente, como segue:
Assinale a alternativa que apresenta, corretamente, uma Expressão Regular (ER) que denota todas as strings de a's e b's que tenham pelo menos dois b's consecutivos: