StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>As for regular languages, there are many equivalent characterizations. They give many different ways of looking at regular languages. It is hard to give a "plain English" definition, and if you find it hard to understand any of the characterizations of regular languages, it is unlikely that a "plain English" explanation will help. One thing to note from the definitions and various closure properties is that regular languages embody the notion of "finiteness" somehow. But this is again hard to appreciate without better familiarity with regular languages.</p> <p>Do you find the notion of a finite automaton to be not simple and clean?</p> <p>Let me mention some of the many equivalent characterizations (at least for other readers) :</p> <ul> <li>Languages accepted by <a href="http://en.wikipedia.org/wiki/Deterministic_finite-state_machine" rel="nofollow">deterministic finite automata</a></li> <li>Languages accepted by <a href="http://en.wikipedia.org/wiki/Nondeterministic_finite_automata" rel="nofollow">nondeterministic finite automata</a></li> <li>Languages accepted by <a href="http://en.wikipedia.org/wiki/Alternating_finite_automaton" rel="nofollow">alternating finite automata</a></li> <li>Languages accepted by <a href="http://en.wikipedia.org/wiki/Two-way_deterministic_finite_automaton" rel="nofollow">two-way deterministic finite automata</a></li> <li>Languages generated by <a href="http://en.wikipedia.org/wiki/Linear_grammar#Relationship_with_regular_grammars" rel="nofollow">left-linear grammars</a></li> <li>Languages generated by <a href="http://en.wikipedia.org/wiki/Linear_grammar#Relationship_with_regular_grammars" rel="nofollow">right-linear grammars</a></li> <li>Languages generated by <a href="http://en.wikipedia.org/wiki/Regular_expression#Formal_language_theory" rel="nofollow">regular expressions</a>.</li> <li>A union of some equivalence classes of a <a href="http://en.wikipedia.org/wiki/Myhill%E2%80%93Nerode_theorem" rel="nofollow">right-congruence of finite index</a>.</li> <li>A union of some equivalence classes of a congruence of finite index.</li> <li>The inverse image under a monoid homomorphism of a subset of a finite monoid.</li> <li>Languages expressible in monadic second order logic over words.</li> </ul>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload