160 questions linked to/from How to prove that a language is not regular?
671 views

### Show this language is non-regular using pumping lemma: B = {ww | w ∈ {a,b,c,…,z)*} [duplicate]

The question I'm working from is: Prove whether or not a finite automation exists that recognises the following language: B = {ww | w ∈ {a,b,c,...,z)*} EDIT So I believe this is a non-regular ...
839 views

546 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 ...
110 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 ...
433 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
423 views

### Pumping Lemma vs Myhill-Nerode [duplicate]

I was searching for a difference on both ways of proving that a language is not regular but I didn't came up with much. Let us take the following as an example: $$L = \{ a^n b^n \mid n \ge 0\}$$ ...
158 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 ...
123 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 ...
119 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.
247 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 ...
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 ...
I have these two languages $L_1={\{a^n b^m,n≥m+5,m>0}\}$ Where $∑=(a,b)$ $L_2={\{a^n b^m,n≥m+5,m≤5}\}$ Where $∑=(a,b)$ As you can see that there is only one difference, the condition of ...