Tagged Questions

Necessary properties of formal langagues in certain classes that rely on closure against repetition of certain subwords.

learn more… | top users | synonyms

2
votes
1answer
21 views

Pumping lemma for 0^n and n>0

When applying the pumping lemma to $L = \{ 0^n \mid n>0\}$ I do the following: $S = 0^p$ $x = \varepsilon$ $y = 0^p$ $z = \varepsilon$ so $S = xyz = (\varepsilon)0^p(\varepsilon)$ For $x y^i z$ ...
2
votes
2answers
82 views

Show that 0^i where i is a power of 2 is not context free

I'm having difficulty trying to use the pumping lemma in order to show that $L= \{0^i \mid \ i \text{ is a power of 2 }\} $ is not context free. I"m starting by stating that $ s = 0^p$ and then $ s = ...
0
votes
1answer
45 views

Pumping Lemma for $L=\{a^{2k} b^n b^k \mid k\ge0, n\ge0\}$

$L=\{a^{2k}b^nb^k\mid k\geq0, n\geq0\}$ over alphabet $\{a,b\}$ How do I prove that $L$ is not regular using Pumping Lemma? All the examples I've come across had same exponents all around, and I'm a ...
0
votes
2answers
61 views

High Level Explanation of the Pumping Lemma

I have a problem that I cannot figure out regarding using the pumping lemma to prove that a language is not regular. I don't understand how I go about proving through contradiction that the language ...
0
votes
1answer
34 views

How to prove that $\{0^n 1^{5n} \mid n \ge 10000 \}$ is not a regular language?

I proved that $$ \{ 0^n 1^{5n} \mid n \geq 0 \}$$ is not a regular language using Pumping Lemma by following way. Solve by contradiction that $ L = \{0^n 1^{5n} \mid n \geq 0 \}$ is regular ...
-1
votes
0answers
13 views

To check L = a^m b^n | m<n is Non Regular by Pumping Lemma [duplicate]

I want to check whether language L = a^m b^n | m < n. By Intuitively it is not Regular as there is comparison between m and n.So require memory which is not possible in FA. But I want to prove it ...
1
vote
2answers
68 views

Show that for any natural number n, there is a regular language that is not recognized by any DFA with at most n final states

Just as the question asks, I am trying to understand the relationship between the number of accept states a DFA has (not necessarily the total number of states) and the languages it can accept. I ...
3
votes
1answer
105 views

Why does this pumping lemma application “prove” that 0*1* is not regular?

Here is a proof that $0^*1^*$ is not regular, even though it is regular. I'm having a hard time figuring out what is wrong with the proof. Assume $0^*1^*$ is regular. Let $p$ be the pumping length as ...
1
vote
1answer
103 views

Can $\{a^mb^nc^n\mid m,n \ge 1\}$ be proved non-regular using the pumping lemma?

$\{a^mb^nc^n\mid m,n \ge 1\}$ intuitively seems like a non-regular language. It looks like the machine needs to remember the number of $b$s (which isn't limited). The pumping lemma can be used to ...
2
votes
1answer
94 views

Prove that the language is not regular without using Pumping Lemma

I am practising problems on Regular Languages and I came across this question: Prove that the language $$\{a^m b^n : m ≥ 0, n ≥ 0, m \ne n\}$$ is not regular. (Using the pumping lemma for this ...
3
votes
3answers
165 views

Clearing a Confusion regarding the Proof of equal no of a's and b's not being a regular language

I was wondering about its proof. The direct use of pumping lemma here is not a viability. So a certain teacher of mine proved this with the notion that $a^{n}b^{n}$ being a subset of this language ...
1
vote
3answers
102 views

Unable to understand an inequality in an application of the pumping lemma for context-free languages

The problem Prove that the language $\qquad L = \{a^n b^j \mid n = j^2\}$ is not context free using pumping lemma. Approach taken by the book To prove such statements, the book takes the ...
0
votes
1answer
45 views

CFL, pumping lemma

I have difficulty with proving that the language $ L = \{ a^p b^q | p \ge 1 , q \ge 1 , p \ge q^2 \vee q \ge p^2\}$ $ w = uvxyz $ I've chosen word $ w = a^{N^2} b^N $ where $ N $ is a constant ...
0
votes
0answers
41 views

Context-free Language, Pumping lemma

I want to prove that $ L = {a^n b^m c^{ \lfloor \frac{n}{m} \rfloor } } $ isn't context free language, so I choose N - constant from lemma so the word is $ w = a^N b^N c $ and $ w = uvxyz $ 1 ...
1
vote
1answer
103 views

requirement for pumping lemma in regular language

I am a bit confused on the theory of the pumping lemma. As I know is used to decide if a language is regular or not. This is what I have understood so far though For a regular language $L$, there ...
-1
votes
2answers
177 views

Using the Pumping Lemma to show that the language $a^n b a^n$ is not regular

I've seen a lot couple of questions regarding the pumping lemma that are pretty similar to each other and this one is unfortunately not the exception. Most likely will be this question marked as a ...
2
votes
1answer
70 views

Is there a Context-free grammar for this language?

Is there a Context-free grammar for the following language: $L=\{ x\#1^m|x \in \{0,1\}^* \space and \space the \space m^{th} \space char \space in \space x \space ...
1
vote
1answer
62 views

Prove not context free

How can we prove that: $$ L = \{ w_1\#w_2 \mid w_1 \in w_2;\; |w_2| > |w_1|;\; w_1 , w_2 \in \{0, 1\}^*\} $$ is not context-free? The language defines $w_1$ as a sub-string of $w_2$, and they ...
1
vote
1answer
71 views

Is the language $L = \{a^nb^m : n = 2^m\}$ context-free?

Is the language $L = \{a^nb^m : n = 2^m\}$ context-free? Assume L is a context-free language. Then $\ \exists p\in \mathbb{Z}^{+}:\forall s\in L\left | s \right |\geq p. s = uvxyz,\left | vy \right ...
-1
votes
1answer
50 views

Show L is not context free using the CFL pumping lemma

I am trying to use the pumping lemma to show this language is not context free: $L = a^nb^{n+1}c^{2n} : n \ge 0$ So I took $z = a^mb^{m+1}c^{2m}$ where $|z| = 4m+1 > m$. We can decompose $z = ...
3
votes
1answer
95 views

Show that the pumping lemmas for context-free and regular languages are equivalent for unary languages

I want to show that for any language $L \subseteq \{ a \}^* $, $L$ satisfies the pumping lemma for context free languages if and only if it satisfies the pumping lemma for regular languages. I know ...
0
votes
1answer
59 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 ...
0
votes
1answer
73 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 ...
0
votes
1answer
84 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
vote
0answers
46 views

Proving a language is regular or non-regular [duplicate]

I'm struggling a bit to understand two of the problems we were given in class. Could someone look over my work and maybe give me a few hints? State whether the following languages are regular or not ...
10
votes
4answers
779 views

Regular language not accepted by DFA having at most three states

Describe a regular language that cannot be accepted by any DFA that has only three states. I'm not really sure where to start on this and was wondering if someone could give me some tips or ...
1
vote
1answer
236 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 ...
1
vote
0answers
20 views

Pumping Lemma Question [duplicate]

I have been trying to solve this question and am kinda stuck. Wondering on how to proceed and finish this proof. Prove that the language $ L = \{a^{2^n} | n >= 0\} $ is not regular. I have been ...
1
vote
3answers
76 views

How can both |y| = 0 and y⁰ = ε hold in the Pumping lemma?

There is something in the pumping lemma that I do not quite understand, namely if $s$ is at least of length $p$, then we could split it to $xyz$ such that the following conditions are met: For each ...
2
votes
1answer
86 views

Is this the correct way to use the pumping lemma?

I've been watching lectures from Coderisland on YouTube about finite state machines, DFAs and NFAs, and in one discussion he talks about how to use the pumping lemma to show how a language is not ...
1
vote
1answer
144 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?
1
vote
1answer
56 views

Is the following language context-free? $L= \{a^nb^m| m\geq2^n\}$

Is $L=\{a^nb^m|m\geq2^n\}$ a context-free language?
1
vote
1answer
183 views

Is L= $\{ww \mid w \in \{a,b\}^*\}$ context-free? [closed]

Let $L = \{ww \mid w \in \{a,b\}^*\}$. In other words, each word of $L$ is some string repeated twice (some string concatenated with itself). Is the language $L$ context-free?
-1
votes
1answer
147 views

Pumping lemma for {w | w = ddd}

I want to use the pumping lemma to show that the following language is not context free: $$ L = \{w \in \{a,b\}^* \mid \exists d \in \{a,b\}^*, w=ddd \} $$ We suppose that $L$ is context-free. Then ...
-1
votes
1answer
82 views

Uncertainty whether $\{a^i b^j c^k \mid i+j \le k\}$ is context-free or not

I'm having trouble with this particular language: $$\{a^i b^j c^k \mid i+j \le k\}$$ If it's not context-free, I don't know how to correctly apply the Pumping Lemma for CFLs; if it is context-free, I ...
0
votes
1answer
53 views

Pumping Lemma for regular language [duplicate]

I have a question to find out that L = {a^(2k)|k>=1} is regular. I know that it is regular set but I was looking to find out if pumping lemma is satisfying or not. So I tried it as - ...
2
votes
2answers
99 views

Is $\{w:w\in(a+b+c)^*, n_a(w) > n_b(w)>n_c(w)\}$ context-free?

So I've been given the following language on an assignment. It is the only question I have left of 10, and I've been racking my brains out trying to solve it for hours. $$L=\{w:w\in(a+b+c)^*, ...
0
votes
1answer
118 views

Context free language and the complement of it

Given the language $L_1 = \{a^i b^j c^k \mid i \neq j \vee i \neq k\}$, I need to determine whether it is context-free by using the pumping lemma. I must do the same for the complement of this ...
-1
votes
1answer
55 views

Context-free Language: deciding z string

Let L = { x in {a,b}* | the number of a are less or equal the number of b^2} I know this is a NOT context free language. How can i choose the correct z=uvwxy and ...
1
vote
1answer
77 views

Using pumping lemma to prove a language is not context free

When using the pumping lemma for a context free language, if I write any $w \in L$ as $uvxyz$, is my goal to show that a string will not pump for ANY arrangement of $uvxyz$ that I choose, or is my ...
4
votes
1answer
441 views

Proving L = {$ { a^{2^n} \ | \ n \ge 0 } $} is not regular by use of Pumping Lemma

I've been struggling with this problem for quite a while now and every explanation I have managed to find doesn't seem to correctly solve it. We have the language L = {$ { a^{2^n} \ | \ n \ge 0 } $} ...
2
votes
2answers
62 views

Can the String, $0^p 0^p 0^p$, be Used with the Pumping Lemma to Show that $w^r w w^r$ is Not Context Free?

I'm trying to show that $L=\left\{w^rww^r:w \in \{0,1\}^*\right\}$ is not context free using the pumping lemma. I thought picking the string, $0^p0^p0^p$, would be a good candidate for this, but ...
1
vote
0answers
20 views

How to show that a languge is not regular [duplicate]

How can I show that this language is not regular? $$ L = \{a^n (ca)^m b^{n+1} \mid m \ge 0 , n \ge 0 \} $$ This is my attempted solution: Assuming the pumping number to be $p$ and making $m=0$ ...
1
vote
2answers
246 views

Is this pumping lemma proof correct?

$$ L = \{a^ib^jc^k \mid i,j,k > 0 \text{ and } i+k>j\} $$ I say it's not regular. Proof by pumping lemma: Find a string $xy^iz$ that is not in $L$ (respecting the constraints). Let ...
1
vote
1answer
232 views

Prove that {0^{n^3} | n≥0} is not context free

I'm not very comfortable with pumping lemma for context-free grammar. I understand the sufficient conditions that must hold but proving it gets me everytime. For example, I need to prove whether $L = ...
1
vote
1answer
204 views

Non context free language that is pumpable? [duplicate]

For my homework assignment, I have to come up with a non-cfl that is pumpable. I came up with the following: $$ C = \{a^n b^n c^n d^m \mid n \ge 1 \text{ and } m \ge 1 \} $$ I'm not sure whether ...
1
vote
1answer
218 views

why does ${a^nb^n}$ fit the pumping lemma for context-free languages?

I am writing somthing about Ppumping Lemma. I know that the language $L = \{ a^nb^n| n ≥ 0 \}$ is context-free. But I don't understand how this language satisfies the conditions of pumping lemma (for ...
2
votes
0answers
38 views

Pumping a Language does not imply regular [duplicate]

I am currently studying the pumping lemma for regular languages and I am trying to come up with an example where even if the language can be pumped it is not regular. Which condition of the lemma ...
0
votes
2answers
244 views

Prove L to not context free using pumping lemma on language L

$L = \{0^i1^j0^i1^j|i,j \geq 0\}$ I've tried letting $s = 0^p1^p0^p1^p$. But not sure where to go from here. Help would be appreciated.
1
vote
1answer
419 views

Proving the language $L= \{0^n 1^m \space | \space m \equiv 0 \space mod \space n, \space n \geq 2 \}$ is not regular using the pumping lemma

I am trying to learn about applying the pumping lemma and I'm not really sure how to go about proving this language isn't regular with the pumping lemma: $L= \{0^n 1^m \space | \space m \equiv 0 ...