157 questions linked to/from How to prove that a language is not regular?
28 views

### How to make finite automaton for this language? [duplicate]

Consider the language $$L = \{0^p 1^q 0^p | p, q ≥ 0\}.$$ How to make a finite automaton for $L$? How to make a regular expression for $L$?
25 views

### Proof by pumping lemma [duplicate]

I'm trying to use the pumping lemma proof to show that the following language is context-free rather than regular $\{ba^n bc^n | n \geq 1\}$ I've been looking at tutorials on Youtube to try and ...
25 views

### How to show that a languge is not regular [duplicate]

How can I show that this language is not regular? $$L = \{a^n (ca)^m b^{n+1} \mid m \ge 0 , n \ge 0 \}$$ This is my attempted solution: Assuming the pumping number to be $p$ and making $m=0$ ...
24 views

### How to apply the pumping lemma to this CF string? [duplicate]

I am struggling understanding how to apply to pumping lemma to a CF string. I've got this string: $$a^{n}b^{n}c^{m}$$ I would like to understand the steps to apply the pumpuing lemma for this ...
21 views

### Pumping lemma with two r languages [duplicate]

I have two questions about how to use pumping lemma for regular languages to show that two languages are not regular. I would appreciate if someone can confirm if my answers make sense, and if not, ...
19 views

### Regular grammar question [duplicate]

Define a regular expression such that there is a string of 1 or more a's continuous followed by a continuous string of b's so that the number of a's and b's are the same. I have ideas on how i would ...
17 views

I was wondering if this language is regular L={$a^{2m+k}b^{3n+l}c^{m+n}$ & $k>2$ & $l \le 3$ & $m,n \in \mathbb{N}$} .I think the regular expression is : $(aa)^*aaa(a)^*(bbb)^* \... 0answers 16 views ### Proof that$L = \{w | na(w) + nb(w) = nc(w)}\ is not regular [duplicate]

So.. my professor mentioned that it has something to do with $Wi = a^5b^i$ $Zij = c^(i+5)$ which is in the language But then mentioned that $Wj = a^5b^j$ $Zij = c^(i+5)$ Is not in the language, ...
15 views

### Struggling with Pumping Lemma application [duplicate]

I have studied Pumping Lemma carefully and have solved many exercises about it but I can't get an idea on how to solve this one: can anyone help me? Let L = { w#x | x is a substring of w }. Prove ...
13 views

### Prove if {a^i b^j | i ≤ j} is a regular language or not [duplicate]

How can i prove if this language is regular or not? (i think is non regular)
70k views

### How to prove that a language is not context-free?

We learned about the class of context-free languages $\mathrm{CFL}$. It is characterised by both context-free grammars and pushdown automata so it is easy to show that a given language is context-free....
There are many methods to prove that a language is not regular, but what do I need to do to prove that some language is regular? For instance, if I am given that $L$ is regular, how can I prove that ...