Como converter um NFA com ciclos sobrepostos em uma expressão regular?

Se bem entendi, a NFA tem o mesmo poder expressivo que as expressões regulares. Freqüentemente, é fácil ler expressões regulares equivalentes do NFA: você traduz ciclos para estrelas, junções como alternativas e assim por diante. Mas o que fazer neste caso:

^{[ fonte ]}

Os ciclos sobrepostos dificultam a visualização do que esse autômato aceita (em termos de expressões regulares). Existe algum truque?

Em vez de "ler", você deve empregar um dos vários métodos canônicos para fazer isso. De longe, o mais bonito que já vi é aquele que expressa o autômato como sistema de equações de linguagens (regulares) que podem ser resolvidas. É particularmente agradável, pois parece produzir expressões mais concisas do que outros métodos.

Eu escrevi este documento explicando o método para os alunos no verão passado. Está diretamente relacionado a uma palestra específica; a referência mencionada é uma definição típica de expressões regulares. Uma prova do lema de Arden (um resultado necessário) está contida; está faltando um para correção do método. Como soube disso na palestra, infelizmente não tenho uma referência.

Resumindo: para cada estado , crie a equação$q_i$

$\qquad \displaystyle Q_i = \bigcup\limits_{q_i \overset{a}{\to} q_j} aQ_j \cup \begin{cases} \{\varepsilon\} &,\ q_i \in F \\ \emptyset &, \text{ else}\end{cases}$

onde é o conjunto de estados finais e q i a → q j significa que há uma transição de q i para q j rotulado com a . Se você ler ∪ como + ou ∣ (dependendo da sua definição de expressão regular), verá que esta é uma equação de expressões regulares.$F$$q_i \overset{a}{\to} q_j$$q_i$$q_j$$a$$\cup$$+$$\mid$

Resolvê-lo (usando o Lema de Arden ) produz uma expressão regular para cada estado que descreve exatamente essas palavras que podem ser aceites a partir de q i ; portanto, Q 0 (se q 0 é o estado inicial) é a expressão desejada.$Q_i$$q_i$$Q_0$$q_0$

A aplicação ao autômato fornecido é deixada como um exercício; um exemplo completo está incluído no documento vinculado acima .

^{Veja também aqui onde eu postei uma resposta semelhante.}

Se houvesse apenas uma cadeia de estados sem loop, você saberia o que fazer?

Se houvesse um loop simples sem essa ramificação sobreposta, você saberia o que fazer?

(Se a resposta for "não", pense nesses casos primeiro.)

Agora, a idéia é transformar o autômato progressivamente para colocá-lo em uma forma em que você possa identificar esses padrões: cadeias, loops e caminhos divergentes que reconvertem no final (levando à alternância). Em cada etapa da transformação, verifique se o autômato transformado ainda reconhece o mesmo idioma.

Lembre-se de que este é um autômato não determinístico. O que você postou é determinístico, mas não precisa ficar assim quando você o transforma.

$q_2$$q_1 \xrightarrow{f} q_2 \xrightarrow{g} q_3$$q_4$$q_2$$q_5$$q_4 \xrightarrow{j} q_5 \xrightarrow{g} q_3$

$q_3,q_4,q_5$$q_3$$q_3$$(hjg)^*$

Tome cuidado para verificar quais estados são finais. Pode ajudar a não se preocupar com isso a princípio e criar um loop grande e, em seguida, duplicar as partes que terminam parcialmente no loop.

Esta não é necessariamente a técnica mais eficiente ou a que gera a expressão regular mais simples, mas é simples.