Linked Questions
158 questions linked to/from How to prove that a language is not regular?
1
vote
1answer
16k 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 ...
3
votes
1answer
7k 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 ...
1
vote
1answer
7k 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?
2
votes
1answer
3k 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 ...
2
votes
2answers
2k 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, ...
0
votes
1answer
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'...
1
vote
1answer
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 ...
-2
votes
2answers
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 |...
2
votes
1answer
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 ...
-1
votes
1answer
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 ...
2
votes
2answers
749 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 ...
0
votes
1answer
1k views
Pumping lemma on {a^n | n=3^k} — help finishing the proof [duplicate]
I am working on a pumping lemma question and trying to prove that the following is not regular, but I can't finish the proof, if someone can help me it will be great.
So I am given this language:
$L ...
-1
votes
2answers
349 views
Finding nfa or dfa for a language [duplicate]
I'm trying to study for the summer ahead of class I saw this question, please how do I go about it?
Find NFA/DFA for the language $L = \{0^n1^n : n \in N\}$
1
vote
1answer
448 views
Non-regular Languages? [duplicate]
Possible Duplicate:
How to prove that a language is not regular?
Why $L_a$ and $L_b$ are not reguluar?
$L_a = \{ e^i f^{n-i} g^j h^{n-j} : n \in N, 1 \leq i, j \leq n \}$.
$L_b= \{nm^{i_1} ...
-1
votes
1answer
820 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
vote
1answer
623 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 ...
0
votes
1answer
978 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 ...
1
vote
1answer
241 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
784 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....
3
votes
1answer
201 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
541 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 ...
2
votes
2answers
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 ...
1
vote
1answer
418 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
1
vote
1answer
396 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\} $$
...
1
vote
1answer
157 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 ...
0
votes
1answer
122 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 ...
-1
votes
1answer
234 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 ...
0
votes
1answer
181 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 ...
-2
votes
1answer
103 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.
0
votes
2answers
131 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 ...