Closure properties to prove regularity, Theory of Computation

The fact that regular languages are closed under Boolean operations simpli?es the process of establishing regularity of languages; in essence we can augment the regular operations with intersection and complement (as well as any other operations we can show preserve regularity). All one need do to prove a language is regular, then, is to show how to construct it from "obviously" regular languages using any of these operations. (A little care is needed about what constitutes "obvious". The safest thing to do is to take the language back all the way to ∅, {ε}, and the singleton languages of unit strings.)

Posted Date: 3/21/2013 1:27:16 AM | Location : United States







Related Discussions:- Closure properties to prove regularity, Assignment Help, Ask Question on Closure properties to prove regularity, Get Answer, Expert's Help, Closure properties to prove regularity Discussions

Write discussion on Closure properties to prove regularity
Your posts are moderated
Related Questions
We'll close our consideration of regular languages by looking at whether (certain) problems about regular languages are algorithmically decidable.

turing machine for prime numbers


automata of atm machine

How useful is production function in production planning?

Describe the architecture of interface agency

The key thing about the Suffx Substitution Closure property is that it does not make any explicit reference to the automaton that recognizes the language. While the argument tha


Normal forms are important because they give us a 'standard' way of rewriting and allow us to compare two apparently different grammars G1  and G2. The two grammars can be shown to