Construção de um FA a partir de um RE

Podemos usar a construção de Thompson para descobrir um autômato finito a partir de uma expressão regular. Reduziremos a expressão regular nas menores expressões regulares e as converteremos em NFA e, finalmente, em DFA.

Algumas expressões básicas de RA são as seguintes -

Case 1 - Para uma expressão regular 'a', podemos construir o seguinte FA -

Case 2 - Para uma expressão regular 'ab', podemos construir o seguinte FA -

Case 3 - Para uma expressão regular (a + b), podemos construir o seguinte FA -

Case 4 - Para uma expressão regular (a + b) *, podemos construir o seguinte FA -

Método

Step 1 Construa um NFA com movimentos nulos a partir da expressão regular fornecida.

Step 2 Remova a transição nula do NFA e converta-a em seu DFA equivalente.

Problem

Converta o seguinte RA em seu equivalente DFA - 1 (0 + 1) * 0

Solution

Vamos concatenar três expressões "1", "(0 + 1) *" e "0"

Agora vamos remover o εtransições. Depois de removermos oε transições do NDFA, temos o seguinte -

É um NDFA correspondente a RE - 1 (0 + 1) * 0. Se você deseja convertê-lo em um DFA, basta aplicar o método de conversão de NDFA em DFA discutido no Capítulo 1.

Autômatos finitos com movimentos nulos (NFA-ε)

Um autômato finito com movimentos nulos (FA-ε) transita não apenas após dar entrada do conjunto de alfabeto, mas também sem qualquer símbolo de entrada. Esta transição sem entrada é chamada denull move.

Um NFA-ε é representado formalmente por uma 5-tupla (Q, ∑, δ, q 0 , F), consistindo em

  • Q - um conjunto finito de estados

  • ∑ - um conjunto finito de símbolos de entrada

  • δ- uma função de transição δ: Q × (∑ ∪ {ε}) → 2 Q

  • q0- um estado inicial q 0 ∈ Q

  • F - um conjunto de estado / estados finais de Q (F⊆Q).

O de cima (FA-ε) aceita um conjunto de strings - {0, 1, 01}

Remoção de movimentos nulos de autômatos finitos

Se em um NDFA, houver ϵ-move entre o vértice X e o vértice Y, podemos removê-lo usando as seguintes etapas -

  • Encontre todas as arestas de saída de Y.
  • Copie todas essas arestas começando de X sem alterar as etiquetas das arestas.
  • Se X for um estado inicial, torne Y também um estado inicial.
  • Se Y for um estado final, torne X também um estado final.

Problem

Converta o seguinte NFA-ε em NFA sem movimento nulo.

Solution

Step 1 -

Aqui a transição ε é entre q1 e q2, então deixe q1 é X e qf é Y.

Aqui, as arestas de saída de q f são para q f para as entradas 0 e 1.

Step 2 -

Agora vamos copiar todas essas arestas de q 1 sem alterar as arestas de q f e obter o seguinte FA -

Step 3 -

Aqui q 1 é um estado inicial, então fazemos q f também um estado inicial.

Então o FA se torna -

Step 4 -

Aqui q f é um estado final, então fazemos q 1 também um estado final.

Então o FA se torna -