Cheap and Secure Web Hosting Provider : See Now

Prove that a language is not regular with process of elimination

, , No Comments
Problem Detail: 

When deterministic automaton, I need to prove that you can't implement the language in it, because the language is not regular.

Easiest way to prove that a language is regular, is just by making an automaton for it. But if the automaton is not regular, you can't just say that it's not regular because you couldn't build an automaton for it.

So I am wondering, how to prove that a language is not regular the simplest way?

Give language:

L = {a^n b^n | n > 0} 

Definition: The language accepts series of a's and b's where the amount of as equals to the amount of bs. This is not a regular language.

How can you prove that it's not a regular language?

From what I remember (I didn't understand it much), you had to take a sub-langauge of that language, and mark it as W

So W = {a^i}

Then select 2 words from W and mark them as w1 and w2

w1 = a^i w2 = a^j 

where i != j

And then I don't really remember what to do.

Asked By : Ben Beri

Answered By : User

A simple technique is using the pumping lemma:

For any regular language $L$ there exists an integer $n$ such that for all $x \in L$, with $|x| \geq n$ there exists $u,v,w \in \Sigma^*$, such that,

  • $x = uvw$
  • $|uv| \leq n$
  • $|v| \geq 1$
  • for all $i \geq 0: uv^iw \in L$

Assumption: Suppose your language is regular.

Consider $s = a^nb^n$. Clearly $s \in L$ and $|s| \geq n$. We get that $uvw = a^nb^n$ and we know that $|uv| \leq n$, i.e $v$ can only contain $a$'s and since $|v| \geq 1$ it must contain at least one $a$. According to the last condition of the pumping lemma, $uv^0w \in L$ but this is clearly not the case. We now have a contradiction as we assumed the language to be regular:

The assumption must be wrong implying non-regularity of the language

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37957

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback