163 questions linked to/from How to prove that a language is not regular?
10k views

### Show that a language consisting of strings of a prime number of 1s is irregular using pumping lemma [duplicate]

Question: L is a language defined as $\ L = \{1^l | l\in primes\}$ (strings of 1s having a prime length). Show that this is not a regular language ($\ L \notin REG$). You may either use the theory ...
21k views

### Is this language regular or non-regular: {ww : w ∈ {a,b}* } [duplicate]

This is a question from a text book that's giving me some trouble. The question is: Determine whether or not this language is regular. Justify your answer. $$L = \{ww : w \in \{a,b\}^* \}$$ I ...
5k views

### Prove that the following language is not regular: $\{0^i1^j : i \neq j\}$ [duplicate]

I was trying to approach this proof, after multiple reads and attempts I am getting nowhere. If someone could help me out that would be great. Should I use the pumping lemma, if so how show I start, ...
8k views

### Proof that {$a^m b^n$ | m!=n} is not regular [duplicate]

I know that the language $\{a^m b^n | n\neq m\}$ satisfies the pumping lemma, but it's still not regular (I have to count the # of a's and b's). How can I formally prove it?
4k views

### Proving that {0^{2^k}} is not regular with the Myhill-Nerode theorem [duplicate]

My language is the repetition of 0 to a length that's a power of 2: $L = \{ 0^k \ni k=2^n, n \geq 1 \}$ I want to know how to prove that this language is not regular. I have attempted the proof ...
1k views

### Union of finite and non-regular language [duplicate]

Question: ($B$ and $C$ are languages) $B$ is finite,$C$ isn't regular: Prove/Disprove: $C\cup B$ isn't regular. Thoughts: My intuition says this is true, but I need an idea to prove it. Since I don'...
2k views

### Prove that the language L = {a^(m+n) b^m a^n | m, n ≥ 0} ∪ {a^m b^n a^(m+n) | m, n ≥ 0} is not regular [duplicate]

In general, how can we go about proving that union of two languages as non regular. In this case, the individual languages can be proved as non regular using pumping lemma. How can we apply pumping ...
1k views

### Prove or disprove whether L is regular [duplicate]

Let $\Sigma = \{0,1\}$. For every word $w \in \Sigma^*$, let $|w|_0$ and $|w|_1$ denote the count of 0's and 1's, respectively, in $w$. Let $L$ be the language L = \{ w \in \Sigma^* \mid |w|_0 \gt |...
2k views

### Irregularity of language of words whose length is of power of 2 [duplicate]

How to show that the language containing the words whose length is a power of $2$, $L=\{w\mid|w|=2^i\}$, isn't regular using the pumping lemma? The pumping lemma says that Let be M a regular language....
1k views

### Proving a language is not regular [duplicate]

I need to prove that the following language is not regular $\{c^mb^na^n \mid n>0,m\geq0\}$ But I am not sure how to do that for this particular one. I vaguely understand pumping lemma, but ...
896 views

### L ={ $a^{m^n}$ | $m$>$n$ } is Regular or not by pumping Lemma [duplicate]

L ={ $a^{m^n}$ | $m$>$n$ } I am bit confuse whether to consider this language as L = $(a^{m})^{n}$ OR L = $a^{\left(m^n\right)}$. If it is considered as L = $(a^m)^{n}$ then want to check it ...
1k views

### pumping lemma for $L=\{a^n b^m c^k \mid n = m \vee m\neq k\}$ [duplicate]

Using pumping lemma, how can I prove that $L=\{a^n b^m c^k \mid n = m \vee m\neq k\}$ is not regular?. If I choose $w= a^m b^m c^m$ and pump up with $i=2$, if have $a^m=1 b^m c^m$ but the string is ...