Linked Questions
160 questions linked to/from How to prove that a language is not regular?
0
votes
1answer
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 ...
-1
votes
1answer
839 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
301 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 ...
0
votes
1answer
988 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 ...
3
votes
1answer
205 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
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 ...
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
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
1
vote
1answer
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\} $$
...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
-2
votes
1answer
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.
-1
votes
1answer
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 ...
0
votes
1answer
183 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 ...
0
votes
2answers
133 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 ...