Geek Answers Handbook

Language Proof

A pumping lemma is used to prove that a language is not regular. But how can the language be found to be regular? In particular,

Let L be a language. Define half(L) to be { x | for some y such that |x| = |y|, xy is in L}. Prove for each regular L that half(L) is regular.

Is there any trick or general procedure to address such issues?

+6
regular-language
source share
2 answers

If you can correctly describe your language L NFA or DFA , then this will be regular.

There is a well-known equality of NFAs, DFAs, regular grammars, and regular expressions , so the representation of L in any of these formalisms must be satisfied.

+9
source share

Provide a regular grammar or state machine appropriate for the language. A complete list of properties that you can prove shows that the language is regular, see the first lines of the Wikipedia article in common languages.

+5
source share

More articles:


All Articles