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

12

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.

Rafael
fonte
2
Você precisa fornecer mais contexto. Qual algoritmo (informal) você está usando no momento para traduzir expressões regulares? Pode ser útil explicar seu processo com um exemplo como a(a|ab|ac)*a+. Você pode traduzi-lo diretamente para um NDFA que reduza para um DFA ou normalizá-lo para algo que mapeie imediatamente para um DFA.
amon
Você precisa fazê-lo em exemplos específicos por qualquer meio ou precisa fornecer um procedimento geral para ser aplicado por um computador?
31515 babou

Respostas:

18

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 vocêLAvocê A linguagem u - 1 Lé chamado dequociente de esquerda(oudeixou derivado) deL.

u1L={vAuvL}
u1LL

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 LA(L)=(Q,A,,L,F)Q={você-1euvocêUMA}F={você-1euvocêeu} , 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 .umaUMA

(você-1eu)uma=uma-1(você-1eu)=(vocêuma)-1eu
UMAeuUMAeueueu

uma,b

a11=0a1b={1if a=b0if aba1(L1L2)=a1L1u1L2,a1(L1L2)=a1L1u1L2,a1(L1L2)=a1L1u1L2,a1L=(a1L)L
a1(L1L2)={(a1L1)L2si 1L1,(a1L1)L2a1L2si 1L1

L=(a(ab))(ba)

11L=L=L1a1L1=(ab)(a(ab))=L2b1L1=a(ba)=L3a1L2=b(ab)(a(ab))(ab)(a(ab))=bL2L2=L4b1L2=a1L3=(ba)=L5b1L3=a1L4=a1(bL2L2)=a1L2=L4b1L4=b1(bL2L2)=L2b1L2=L2a1L5=b1L5=a(ba)=L3
which gives the following minimal automaton. The 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
fonte
Can you say more about the complexity of this algorithm?
babou
@babou Converting a RE to a DFA is PSPACE-hard, so it's definitely exponential.
jmite
This should probably go into the answer. The OP starts with "the standard constructions via NFA are too slow" and part of the answer seems to be "bad luck, there isn't really a fast solution". It remains to discuss whether this here is better than the standard construction. (cc @jmite)
Raphael
@jmite Yes I was expecting that. The reason for my question is why this way of building the DFA should then be considered easier. (note: the system took a full day to notify me of @ jmite answer).
babou
2

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.

jmite
fonte
-2

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.

Naveen CS
fonte