If you want to make money online : Register now

[Solved]: Show language is not regular

, , No Comments
Problem Detail: 

Show that the following languages are not regular in two ways: first by using closure properties then by using the Pumping lemma:

$$\text{(1) L1} = {a^n b^k c^{n+k} : n >= 0; k >= 0}$$

$$\text{(2) L2} = {a^n b^k : n \ne k}$$

So far for

  1. What I tried: Assume that L is regular. By P.L, there exists a P such that $w = a^pb^pc^{2p}$ there is $w_i = xy^iz , \mid y \mid \ge 1 , \mid xy \mid \le p $. We can imply $y = a^k$ and assuming k = 1 $w_0 = xy^0z = xz = a^{p-1}b^pc^{2p}$ which is not an element in L. Therefore there a contradiction and it is not regular. I don't know what to do for the closure properties
  2. Assume that L is regular. By P.L, there exists a P such that $w = a^pb^p$ from here im lost since it says $n \ne k$ for 2) can we say that $ w \notin L $ since $n = p = k$ thus it is a contradiction?
Asked By : Darkflame

Answered By : Rick Decker

For these hints, I'm assuming that you know (and are allowed to use) the fact that $\{a^nb^n\mid n\ge 0\}$ is not regular.

For (1), if $L_1$ was regular, then since regular languages are closed under intersection, we'd have $L_1\cap b^*c^*$ was regular. What's that language?

For (2), if $L_2$ was regular, then since regular languages are closed under complementation, we'd have $\overline{L_2}$ was regular, and so $\overline{L_2}\cap a^*b^*$ was regular. What's that language?

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback