Linked Questions

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 ...

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?

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 ...

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 ...

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'...

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 ...

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 |...

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 ...

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} ...

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 ...

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 ...

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\}$

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 ...

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 ...

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 ...

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^...

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 \...

$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 ...

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 ...

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 ...

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

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 ...

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 ...

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 ...

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 ...

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 ...

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'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 ...

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 ...

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 ...