Formal languages NFA and DFA?
The usual procedure is to construct an NFA (nondeterministic automaton) from a language L(G) with a grammar. Then, from the NFA, a DFA (deterministic automaton) is constructed, and from this, the language with its grammar L(G) is derived.
L(G) to NFA to DFA to LG?
What I am wondering now is, can one also proceed the other way around, i.e. one can create a DFA from an L(G) and then an NFA from this and then derive one's grammar from this?
Or is this procedure much more complicated than
LG to DFA to NFA to LG
(2 votes)
Loading...
A DFA is an NFA. It is also not quite clear to me what exactly now is the difference between the first L and the second L. But you can convert them in both directions, are equivalent.
The L(G) is always the same language with the same grammar!
Why is it usually converted from L(G) to NFA to DFA to L(G).
It’s like a cycle
Why not go from L(G) to DFA to L(G)
That’s my question. Is this way more complicated?
And how do you make an NFA from a DFA?
We’ve always turned from an NFA to a DFA.
You can also go directly from L(G) to the DFA. You have to think more in your head.
You can convert everything into everything, that is shown by the cycle.
Each DFA is also an NFA.
Okay, thanks.
But you can convert any NFA into a DFA?
No.
An NFA can have epsilon transitions and the like. It must not have a DFA.
But each NFA can be converted into a DFA (by means of a potency quantity construction).
Weng confusing but okay. And each NFA is also a DFA. Right?