Linked Questions

3
votes
1answer
165 views

How to prove for that a given non-regular language its given super-set is also non-regular? [duplicate]

Consider the non-regular language $L_1$ = {$a^n$b$a^n$: $n \geq 0$} and its super-set language L = Language of strings with equal number of trailing and leading a's, or in other words, $$L = \{a^...
-1
votes
1answer
390 views

Proving that a language given by a CFG is not regular [duplicate]

Consider the language defined by the following grammar: $$ \begin{align*} &S \rightarrow E \\ &S \rightarrow \epsilon \\ &E \rightarrow E+E \\ &E \rightarrow E-E \\ &E \rightarrow \...
-1
votes
1answer
361 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 ...
1
vote
1answer
259 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 ...
1
vote
1answer
148 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 ...
1
vote
1answer
283 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
0
votes
1answer
111 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 ...
0
votes
2answers
129 views

How to prove that these two languages are regular, or not regular? [duplicate]

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 ...
0
votes
1answer
94 views

Prove this language is non-regular [duplicate]

I'm struggling to understand this question using pumping lemma to prove a language is not regular. Any help would be appreciated. Prove using the Pumping Lemma that the following language is not ...
1
vote
3answers
173 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 ...
2
votes
1answer
100 views

How to prove that $L_1=1^*\cup \{0^i 1^{j^2}|i\ge 0,j\ge 0\} $ is irregular? [duplicate]

We know that $L=\{0^i 1^{j^2}|i> 0,j\ge 0\} $ is irregular (by the Pumping Lemma), we have to use it to prove two things: $L_1=1^*\cup \{0^i 1^{j^2}|i\ge 0,j\ge 0\} $ is irregular. $L_1$ is ...
0
votes
1answer
116 views

Why are these languages not regular? [duplicate]

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 ...
1
vote
1answer
138 views

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 ...
1
vote
2answers
75 views

Prove that a language is not regular with process of elimination [duplicate]

When deterministic automaton, I need to prove that you can't implement the language in it, because the language is not regular. Easiest way to prove that a language is regular, is just by making an ...
0
votes
1answer
122 views

Pumping lemma not regular [duplicate]

How would about proving this is not regular with the pumping lemma. Please include all steps and explain all steps. I am really new with this. $1^{2x}0^y$ and $y>= x$ Does it matter which side ...

15 30 50 per page