How to prove a language is regular?
There are many methods to prove that a language is not regular, but what do I need to do to prove that some language is regular?
For instance, if I am given that $L$ is regular, how can I prove that the following $L'$ is regular, too?
$\qquad \displaystyle L' := \{w \in L: uv = w \text{ for } u \in \Sigma^* \setminus L \text{ and } v \in \Sigma^+ \}$
Can I draw a nondeterministic finite automaton to prove this?
Asked By : corium
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/1331
Answered By : Ran G.
Yes, if you can come up with any of the following:
- deterministic finite automaton (DFA),
- nondeterministic finite automaton (NFA),
- regular expression (regexp of formal languages) or
- regular grammar
for some language $L$, then $L$ is regular. There are more equivalent models, but the above are the most common.
There are also useful properties outside of the "computational" world. $L$ is also regular if
- it is finite,
you can construct it by performing certain operations on regular languages, and those operations are closed for regular languages, such as
- intersection,
- complement,
- homomorphism,
- reversal,
- left- or right-quotient,
- regular transduction
and more, or
- using Myhill–Nerode theorem if the number of equivalence classes for $L$ is finite.
In the given example, we have some (regular) langage $L$ as basis and want to say something about a language $L'$ derived from it. Following the first approach -- construct a suitable model for $L'$ -- we can assume whichever equivalent model for $L$ we so desire; it will remain abstract, of course, since $L$ is unknown. In the second approach, we can use $L$ directly and apply closure properties to it in order to arrive at a description for $L'$.
Post a Comment