World's most popular travel blog for travel bloggers.

# [Solved]: Show language is not regular

, ,
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?

#### 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

#### Post a Comment

Let us know your responses and feedback