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

learn more… | top users | synonyms

1
vote
3answers
74 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
35 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
36 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
88 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
136 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
56 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
58 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
59 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
46 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
80 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
56 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
54 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
73 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
44 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
569 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
201 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
19 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
74 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
75 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
110 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
49 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
162 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
146 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
76 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
42 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
94 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
114 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
54 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 ...
2
votes
1answer
58 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 goal to ...
4
votes
1answer
218 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
60 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
214 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
193 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
195 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
160 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
228 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
372 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 ...
3
votes
3answers
146 views

Decide if L is regular or not and argue it. Trying to use Pumping Lemma

Part (a): Let $L = \{x \in \{0,1\}^* \mid \#0(x) \neq 4\times\#1(x)\}$, where $\#0(x)$ means the number of 0 in string $x$ and $\#1(x)$ means the number of 1 in string $x$. So I want to use the ...
1
vote
1answer
57 views

Concatenation among different language types

I am trying to figure out the result of the concatenation among different language types (regular, context free, ...). I think the result strongly depends on the nature of the languages which will be ...
4
votes
3answers
690 views

Is the language that accepts strings concatenated with their reverse regular?

If the set of regular languages is closed under the concatenation operation and is also closed under the reverse operation ($x^R$ is the reverse of $x$) then is the language generated by ...
1
vote
1answer
75 views

The language of all borderless words

Could anyone help me please to find who was the first person who has proved that the language of all borderless words is not regular and when was that? Could you mention the reference, please? A word ...
1
vote
3answers
172 views

Is $L = \{a^jb^ia^{j-i}\mid i,j \ge 0\ , j > i\}$ context-free?

I'm exercising for an upcoming exam and I find this exercise: Say whether or not the language $$L = \{a^jb^ia^{j-i}\mid i,j \ge 0\ , j > i\}$$ is a context-free language. Justify your ...
9
votes
1answer
266 views

Is the language of words containing equal number of 001 and 100 regular?

I was wondering when languages which contained the same number of instances of two substrings would be regular. I know that the language containing equal number of 1s and 0s is not regular, but is a ...
6
votes
3answers
789 views

Example of a non-context free language that nonetheless CAN be pumped?

So basically L satisfies the conditions of the pumping lemma for CFL's but is not a CFL (that is possible according to the definition of the lemma).
2
votes
2answers
166 views

Is {xyx | |x|≥1} context-free?

Is $L=\{ xyx \mid x,y \in \{a,b\}^* \text {and } |x| \ge 1 \}$ context-free? If yes, please explain how we can write grammar or create a PDA for it. If not a CFL, then prove it through pumping ...
1
vote
1answer
67 views

Is the language $a^{3}b^{+}$ the same as $\{a^{3}b^{n}, n \geq 1\}$ ? and what is the result of pumping this?

The regular expression $a^{3}b^{+}$ is indeed regular because we can define an automata $M$. But I see that $\mathcal{L} = \{a^{3}b^{n}, n \geq 1\}$ may generate the same strings, but using the ...
20
votes
3answers
814 views

Is this strange language context free?

Is the following language context free: $L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^+, |u| = |v|, u \neq v, |x| = |y|, x \neq y\} $ ? I think that it's not context free but I'm having a hard time proving ...
2
votes
1answer
166 views

Prove that context free languages are not closed under swapping prefixes and suffixes

Prove that context free languages aren't closed under this operation: $ A(L) = \{ zyx \mid x,y,z \in \{0,1 \}^*, xyz \in L \} $ Obviously, we need to find a context free language $L$ such that $A(L)$ ...