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

1k views

Using the pumping lemma for a proof by contradiction [duplicate]

I'm trying to prove that the set of even-length strings with the two middle symbols being equal cannot be accepted by finite automata. I can explain why it cannot be accepted intuitively, but I'm ...
219 views

575 views

Proving a grammar/language as not regular [duplicate]

$D → T ∨ D | T$ $T → C ∧ T | C$ $C → ¬C | name | ( D )$ $name → a | b | c | d$ I am not looking for the complete answer, but more the methodology of working this out. How would I go about proving ...
119 views

Class of a Language [duplicate]

What are the common ways to check if a given language is regular, context free, or context sensitive? Any surveys or notes would also be helpful. There's no need to describe your suggestions. eg. it ...
460 views

proving {$a^ib^jc^k : j = i \lor j = k$} is not regular [duplicate]

i had troubles proving this is not regular using the pumping lemma {$a^ib^jc^k : j = i \lor j = k$}. Not sure how to approach this anymore, and help would be appreciated
199 views

Provide "regular" grammar for this language {${a^ib^j \mid i>0\ and \hspace{2.5mm}i\leq j \leq(2*i)}$} [duplicate]

I'm trying to understand the approach to constructing an grammar which accepts the language ${a^ib^j \mid i>0\ and \hspace{2.5mm}i\leq j \leq(2*i)}$ } Thanks.
162 views

Proving a language is not a regular language but a context free language [duplicate]

I have the languages $L_1$ and $L_2$ such that $L_1 = \{a^nba^n :n \in N\}$ and $L_2 =\{a,b\}^*\setminus L_1$. I want to prove that $L_2$ is not a regular language. I know that to prove that $L_2$ is ...
308 views

Proving a language is non-regular using the Pumping Lemma for non-binary strings [duplicate]

I am unsure of how to prove this language is non-regular. I do not even know where to start to develop a string that would prove the language is non-regular by contradiction. Any help would be ...
124 views

Showing that $\{ c^n a^m b^{n+m} : n+m \geq 6\}$ is not regular [duplicate]

I'm trying to show that $L_6=\{c^n a^m b^p : n+m=p,p \geq 6\}$ is not regular. I need a little help, I was practicing the pumping lemma, and I encountered this language, I saw these conditions and got ...
Show that the following languages are not regular: $(1)\ L=\left\{a^nb^mc^k\mid n>k \land n,m,k>0\right\}$ $(2)\ L=\left\{a^nb^mc^k\mid m>k \land n,m,k>0\right\}$ I've difficulties ...
How to show that $L=\{ wa^kw | w \in \{ a,b,c \}^* ,k \geq 0 \}$ is not regular using the pumping lemma for regular languages? [duplicate]
I'm trying to show that the language in the title is not regular but I don't know how to chose a decomposition $x = abc$ to express the word in the language because the $w \in \{a,b,c\}^*$ is kinda ...