質問

As the title suggests, how are DFA and NFA related to regular expressions? Would learning DFA and NFA be useful in having a better understanding in regular expressions?

役に立ちましたか?

解決

Finite automata (fa), regular expression(re), and also regular grammars, all are finite representation for regular languages. The purpose all of them is to express a regular set/language (and same is true for other class of languages like cfg, csl etc).

Automata comparatively more useful for theoretical purpose, to analysis language properties — class of complexity.

In case of finite automata, both deterministic (DFA) and non-deterministic (NFA) models represent same class of language, called "regular language" (that is not true for other languages for npda ≭ pda).

Regular expression (re): is another way to represent regular languages in alphabetical form, which is very much helpful to represent a set of valid strings in programming languages (here automata can't be useful directly whereas regular expression is not much helpful to analysis language properties eg. to fully describe pumping lemma).

How are DFA and NFA related to regular expressions?

  • Both represent same class of languages — regular languages
  • Its not possible to construct automata or regular expression algorithmically from English description of language directly. Although, if we have any one representation (FA or RE) then we can systematically write other representation eg.we can write regular expression for a DFA/NFA in step by step and systematic manner, using Arden's theorem. (check this link)

    Lets take a language example: L = "Even number of a's and b's".

    regular expression for L is:

    (
     (a + b(aa)*ab)(bb)*(ba(aa)*ab(bb)*)*a +
     (b + a(bb)*ba)(aa)*(ab(bb)*ba(aa)*)*b
    )*
    

    Its very tough to write regular expression for this language directly(even its bit typical to understand this re quickly).

    But from DFA and using Arden't theorm it was simple to write regular expression for language L.

    Important is that drawing DFA for this language is comparatively simple (also easy to memorize).

    One more example can be language over "symbols 0 and 1, where decimal equivalent of binary string is divisible by 5", writing RE for this will be very hard compare to writing DFA.

  • We can also draw DFA from a regular language algorithimally.

Would learning DFA and NFA be useful in having a better understanding in regular expressions?

Yes, because of following reasons:

  • Sometime it is hard to write RE directly.
  • A regular expression that is written directly from English description can be buggy. Chances of buggy dfa would be less than buggy regex that is why when we writing compiler for some language then preferable/correct steps are considered to draw DFA first from each token, then write their equvilent regex — DFA will be consider proof of correctness - dfa are more descriptive and easy to grasp language construct (DFA is correct then RE will be correct).

  • If re is complex and you are to find "what is the language description?", then you can draw DFA from re and then give language description.

  • Sometime to find better re, you can draw DFA then translate it to minimize DFA then write re using minimized DFA may give you better solution. (Its not general technique, may be helpful sometime)

  • If its hard to compare two regular expressions then you can compare their corresponding DFAs to check for equivalence.

Note: Sometime writing regular expression is much simpler then drawing DFAs.

他のヒント

A non-deterministic finite automaton (NFA) is a machine that can recognize a regular language.

A regular expression is a string that describes a regular language.

It is possible to algorithmically build an NFA that will recognize the language described by a given regular expression. Running the NFA on an input string will tell you if the regular expression matches the input string or not.

So NFAs can be used to implement regular expression engines, but knowledge of them is not required to use regular expressions to their full potential.

ライセンス: CC-BY-SA帰属
所属していません StackOverflow
scroll top