Como criar DFA a partir de expressões regulares sem usar o NFA?

O objetivo é criar o DFA a partir de uma expressão regular e o uso de "Exp regular> NFA> conversão do DFA" não é uma opção. Como alguém deveria fazer isso?

Fiz essa pergunta ao nosso professor, mas ele me disse que podemos usar a intuição e se recusou a fornecer qualquer explicação. Então, eu queria perguntar a você.

"Exp exp> NFA> conversão DFA" não é uma opção porque essa conversão leva muito tempo para converter uma expressão regular bastante complexa. Por exemplo, para um certo regex "regex> NFA> DFA", leva 1 hora para um ser humano. Preciso converter regex para DFA em menos de 30 minutos.

Como você deseja "converter regex em DFA em menos de 30 minutos", suponho que você esteja trabalhando manualmente em exemplos relativamente pequenos.

Nesse caso, você pode usar o algoritmo de Brzozowski , que calcula diretamente o autômato Nerode de uma linguagem (que é conhecido por ser igual ao seu autômato determinístico mínimo). Baseia-se no cálculo direto das derivadas e também funciona para expressões regulares estendidas, permitindo interseção e complementação. A desvantagem desse algoritmo é que ele requer a verificação da equivalência das expressões computadas ao longo do caminho, um processo caro. Mas, na prática, e para pequenos exemplos, é muito eficiente.$[1]$

Quocientes à esquerda . Deixe ser uma língua do A * e deixe u ser uma palavra. Então $L$$A^*$$u$ A linguagem u - 1 Lé chamado dequociente de esquerda(oudeixou derivado) deL.

$$u^{-1}L = \{v \in A^* \mid uv \in L \}$$ $u^{-1}L$$L$

Autómato Nerode . O autômato Nerode de é o autômato determinístico A ( L ) = ( Q , A , ⋅ , L , F ) onde Q = { u - 1 L ∣ u ∈ A ∗ } , F = { u - 1 L ∣ u ∈ L } e a função de transição é definida, para cada a $L$$\mathcal{A}(L) = (Q, A, \cdot, L, F)$$Q = \{u^{-1}L \mid u \in A^*\}$$F = \{u^{-1}L \mid u \in L\}$ , pela fórmula ( u - 1 L ) ⋅ a = a - 1 ( u - 1 L ) = ( u a ) - 1 L Cuidado com esta definição bastante abstrata. Cada estado de A é um quociente esquerdo de L por uma palavra e, portanto, é uma linguagem de A ∗ . O estado inicial é a linguagem L , e o conjunto de estados finais é o conjunto de todos os quocientes esquerda do L por uma palavra de L .$a \in A$

$$(u^{-1}L)\cdot a = a^{-1}(u^{-1}L)=(ua)^{-1}L$$ $\mathcal{A}$$L$$A^*$$L$$L$$L$

$a, b$

$$\begin{align*} a^{-1}1 &= 0 & a^{-1}b &= \begin{cases} 1 &\text{if $a = b$}\\ 0 &\text{if $a \not= b$}\\ \end{cases}\\ a^{-1}(L_1 \cup L_2) &= a^{-1}L_1 \cup u^{-1}L_2,& a^{-1}(L_1 \setminus L_2) &= a^{-1}L_1 \setminus u^{-1}L_2,\\ a^{-1}(L_1 \cap L_2) &= a^{-1}L_1 \cap u^{-1}L_2, & a^{-1}L^* &= (a^{-1}L)L^* \end{align*}$$ $$\begin{align*} a^{-1}(L_1L_2) &= \begin{cases} (a^{-1}L_1)L_2 &\text{si $1 \notin L_1$,}\\ (a^{-1}L_1)L_2 \cup a^{-1}L_2 &\text{si $1 \in L_1$}\\ \end{cases}\\ %\\v^{-1}(u^{-1}L) &= (uv)^{-1}L. \end{align*}$$

$L = (a(ab)^*)^* \cup (ba)^*$

$$\begin{align*} 1^{-1}L &= L=L_1\\ a^{-1}L_1 &=(ab)^*(a(ab)^*)^*=L_2\\ b^{-1}L_1 &= a(ba)^*=L_3\\ a^{-1}L_2 &= b(ab)^*(a(ab)^*)^* \cup (ab)^*(a(ab)^*)^*=bL_2 \cup L_2=L_4\\ b^{-1}L_2 &=\emptyset \\ a^{-1}L_3 &=(ba)^*=L_5\\ b^{-1}L_3 &=\emptyset \\ a^{-1}L_4 &= a^{-1}(bL_2 \cup L_2)=a^{-1}L_2=L_4 \\ b^{-1}L_4 &= b^{-1}(bL_2 \cup L_2)= L_2\cup b^{-1}L_2 = L_2 \\ a^{-1}L_5 &= \emptyset\\ b^{-1}L_5 &=a(ba)^*=L_3 \end{align*}$$ which gives the following minimal automaton.

$[1]$ J. Brzozowski, Derivatives of Regular Expressions, J.ACM 11(4), 481–494, 1964.

Edit. (April 5, 2015) I just discovered that a similar question: What algorithms exist for construction a DFA that recognizes the language described by a given regex? was asked on cstheory. The answer partly addresses complexity issues.

J.-E. Pin provides the better answer in terms of formality and completeness, but I think there's something to be said for the "intuition" that your professor is hinting at.

In most of these cases, the easiest thing to do is to look at a regular expression, understand what language it's accepting, then use your creativity/cleverness to construct a DFA accepting that language.

There's no straightforward way to do this, other than the algorithms others have given, but here are some guidelines that might prove useful.

1. Ask yourself, could I write a program that accepts this RE using only boolean or very small integer variables? Then write that program, and convert it into a DFA where there's a state for every combination of values.

2. Look for parts of the regular expression that you know you can accept deterministically, where you know "If I see this, then I must be matching this part of the RE." There won't always be tons of these, but identifying these parts can show the parts that will be easy to make a DFA, so you can spend more time on the parts that really require non-determinism.

3. The subset construction for NFA->DFA isn't actually that complicated of an algorithm. So if this is an assignment, not an exam question, it might be faster to just code up an implementation, and let your program convert NFA to DFA. If you used your own code, there shouldn't be any plagarism issues.

Remember that no matter what you do, any technique will blow up exponentially in the worst case (unless you find a polynomial algorithm for this, in which case, congratulations, you've proved $P=NP=PSPACE$ and you're now a millionaire.)

Try to "look ahead," cut corners when you can use your intuition in places when the algorithm would require many steps but its result is clear.

Though this is not the correct way but it works most of the time.

First Step : Find the smallest string that can be accepted by the Regular Expression. Second Step : Draw necessary states with the transaction of the minimum string accepting machine. Third Step : For all states draw the remaining alphabets transactions.

For Example : Regular Expression (0 + 1)* 1 "String ending with 1" Step 1: Smallest String : 1 Step 2: two states Q0 and Q1. having the transaction of 1 from Q0 to Q1. and Q1 is the accepting state. Step 3: for Q0 State Q0 1 transaction is to Q1. Now make 0 transaction in Q0 itself. For Q1 State Q1 1 transaction will remain in Q1. And 0 transaction will go in Q0.