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

learn more… | top users | synonyms

-1
votes
0answers
12 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
62 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
90 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
88 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 ...
-1
votes
0answers
55 views

Theory of computation - Proving that a language is non-regular [on hold]

I learned about the Pumping Lemma in class a couple of lectures ago, and after reading my book/other sources online I think I have come to understand it. I am doing sample exercises like the one ...
2
votes
1answer
73 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
156 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
98 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
43 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
39 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
101 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
170 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
67 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
60 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
65 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
49 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
90 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
68 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
747 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
233 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
75 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
83 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
141 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
53 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
174 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
80 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
47 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
98 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
117 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
73 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
415 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
239 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
208 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
201 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
204 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
235 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
407 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
149 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
58 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
866 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
76 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 ...