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
17 views

Pumping lemma regular language can't be pumped

Suppose we have a regular language that describes every string with the exact length of 3.That is obviously a regular language and it still can't be pumped because there is no cyclic behavior in that ...
4
votes
1answer
89 views

What's wrong with my pumping lemma proof?

The language $L = \{0^{2n} \space |\space n \ge 0 \}$ is obviously regular – for example, it matches the regular expression $(00)^*$. But the following pumping lemma argument seems to show it's ...
1
vote
1answer
42 views

Showing that the pumping lemma cannot prove that some language is not regular

I have this language $ L = a^* \cup \left \{ a^mb^n|m>n\geq 0 \right \}^* $ I have to prove that this language is not regular but still satisfies the pumping lemma for regular languages (Since the ...
3
votes
1answer
41 views

Proving that if $L=\{ a^n b^n c^n \colon n\ge 0 \}$ than $L\notin CFL$ [closed]

I'm going over "Introduction to the Theory of Computation" by Michael Sipser in which there's an example of using the pumping lemma for CFLs to prove that $L=\{ a^n b^n c^n \colon n\ge 0 \}$ is not a ...
-1
votes
1answer
144 views

Does every language that fulfills the regular Pumping conditions also fulfill the context-free ones?

Let L be a language that fulfills the properties implies by the Pumping lemma for regular languages. Does L necessarily fulfill the corresponding properties of the Pumping lemma for context-free ...
0
votes
0answers
58 views

The pumping lemma - Proving that this language is NOT context free

I would like to find out if this language is context free or not: $\qquad L=\{a^{i}b^{j}c^{k} \mid i<j,i+2j+3<k\}$. I've tried to apply the pumping lemma taking out $w=a^n b^{n+1}c^{3n+6}$ ...
0
votes
1answer
67 views

Using the pumping lemma to prove that a language is context-free [duplicate]

I am new to automata theory. Could you give me a little hand with the correct use of the pumping lemma? I understand now how to proof a language is not context-free, but how do I use the pumping ...
0
votes
1answer
46 views

How to prove that the language { ww | w ∈ {a,b}* } is / isn't context free? [duplicate]

Is the language { ww | w ∈ {a,b}* } context free? I have tried to create a pushdown automaton but I didn't find any solution. I think you need a queue and not a stack. Is there a way to prove this ...
0
votes
1answer
79 views

Is the language $L=\{a^{2^{n}} \mid$ n is a natural number$\} $ context free?

I have to determine, and prove, whether the language $L=\{a^{2^{n}} \mid$ n is a natural number$\}$ is context free or not (if it is by a grammar and not by the pumping lemma). I tried to construct ...
1
vote
1answer
44 views

Irregularity of L = {a^i b^(j+3)| i!=j }

I have a question to find out that $L = \{a^i b^{j+3}\mid i\ne j \}$ is regular or not. I know that it is not regular. I tried with pumping lemma but I am finding just a specific number of $v$'s in $u ...
-1
votes
1answer
40 views

Use the pumping lemma to show that the language is not regular [closed]

I am working on this problem : Use the pumping lemma to show that the language $\{0^n 1^{n} \mid n ≥ 1\}$ is not regular. May someone give me some suggestion about how to solve this problem?
-1
votes
1answer
64 views

Proving a language isn't regular using the pumping lemma [closed]

Let the language $$ L = \{ a^nb^m : m,n \text{ has the same integer-quotient, (ignoring the remainder) } \} $$ Show that $L$ isn't regular using the pumping-lemma. Let's assume by contradiction ...
1
vote
1answer
48 views

Proof that a language is not regular using pumping lemma

I have a language $L$ that I think is not regular: $L = \{w\in \{0,1,...,9\}^* \; | \enspace w \enspace \text{is a decimal representation of a number divisible by 3}\}$ I'm using pumping lemma in my ...
0
votes
0answers
24 views

Ogden’s lemma on CFG

I'm trying to understand Ogden's lemma, and I know there are 4 cases, but in the next example I can only find 3: Assume A = {$0^n1^m0^k$ | k = $max${n, m}} is CF: Choose z = $0^k1^k0^k ∈ A$, z = ...
1
vote
1answer
35 views

When to pump up and down?

When I'm solving a question I usually spent too much time testing whether I should pump or down? Is there any formula to know when to use which? Also, on proofing non context free grammar we use ...
-1
votes
1answer
51 views

pumping lemma for $L=\{a^n b^m c^k \mid n = m \vee m\neq k\}$ [duplicate]

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 ...
3
votes
1answer
41 views

Is the language of all $a^n$ for which $n$ has an even number of digits in 10-base system regular?

Is the language $ L = \{a^n ~| ~n \text{ has even number of digits in 10-base system}\} $ regular? My approach: let the $ p $ be from the Pumping Lemma. Chose the smallest $ n $ which has even number ...
0
votes
2answers
74 views

Verification wanted: Show the language $L=\{0^m1^n \enspace | \enspace m \neq n\}$ is not regular [closed]

$$L=\{0^m1^n \enspace | \enspace m \neq n\}$$ I saw that this exact question exists elsewhere, but I couldn't understand what was being said there. My question does not mandate the use of the Pumping ...
0
votes
1answer
59 views

Proving that $L=\lbrace{ab^{n}ba^{n}|n\geq1}\rbrace$ is not regular with pumping lemma

I'm trying to understand the pumping lemma for regular languages and would like to prove that $L=\lbrace{ab^{n}ba^{n}|n\geq1}\rbrace$ is not regular. My suggestion is as follows: Assuming ...
3
votes
1answer
61 views

A non-regular language satisfying the pumping lemma

I got a problem to solve, which is to demostrate that the language $L$, given by: $L = \{ab^nc^n\mid n \geq 0\} \cup \{a^kw \mid k\geq 2 \wedge w \in \Sigma^*\}$ Satisfies the pumping lemma. Is not ...
0
votes
0answers
43 views

The pumping lemma for the context free languages [duplicate]

I am trying to use the pumping lemma to show this is not a context free language $$ L = \{a^n b^{2n} a^n\mid n\ge 0\} $$ My idea is fist assume it is a CFG language and let $n$ be the pumping lemma ...
0
votes
0answers
28 views

$L = \{a^{n^3} | \ge 0\}$ Use the Pumping Lemma to show that L is not regular [duplicate]

Use the Pumping Lemma to show that $L$ is not regular: $$ L = \{{a^{n^3} | \ge 0}\}$$ I feel like I have a good intuition of what the Pumping Lemma states; strings that belong to a regular language ...
-2
votes
2answers
59 views

I think I have a regular expression for a non-regular language

Let $W = \{a^n b^m \mid n\ge m+5,m\le 5\}$, where $\Sigma=\{a, b\}$. I have proved that this language is irregular through pumping Lemma. But through regular expression it is proving that the ...
0
votes
1answer
44 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 ...
0
votes
2answers
75 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 ...
0
votes
1answer
26 views

Pumping lemma of regular language [duplicate]

I was wondering in how to solve this question, I feel a bit confused: for $\Sigma = \{1,\#\}$, consider $$D=\{w \mid w=x_1 \# x_2 \# \cdots \# x_k \text{ for } k \geq 0, \text{ each } x_i \in 1^*, ...
3
votes
1answer
158 views

How does a regular language satisfies the second condition of the pumping lemma

I'm a little bit confused about the second condition of the pumping lemma which are: $|y|\geq1$ $|xy|\leq p$ $\forall i \geq 0:xyiz\in L$ I don't understand why the length of ...
0
votes
1answer
105 views

Pumping Lemma confusion

I have the following language... $$A=\{a^ib^i | i>0\}\cup\{a^jb^k|j>2, k>3\}$$ Now, pumping lemma states that a regular language can be written in the form $x=pq^ir$. What confuses me is ...
0
votes
1answer
52 views

Pumping Lemma for Regular Language seems to Fail

Let $L = \{ab^ncd \mid n \geq 0\}$. If we take $p = 5$ and $w = abbcd$ and write $w_i = xy^iz$, where $x = abb$, $y=c$, $z=d$, then $w_2 = abbccd$ which is not in $L$. We conclude that ...
0
votes
1answer
102 views

How do I show that $a^n w b^n$ is not regular?

Given $ \Sigma= \{a,b\} $, show that $ L:= \{a^nwb^n: m,n \in \mathbb N, m\geqslant n, w\in\Sigma^m\} $ is not regular. I'm trying to proof this with the Pumping Lemma, but I'm kind of confused ...
-1
votes
1answer
118 views

Pumping Lemma Proof by contradiction [duplicate]

So, hi guys! I have a language which I am trying to prove that it is not regular using the Pumping Lemma. I am pretty new into the lemma so I would appreciate any help.The language is $$L = \{w | w ...
1
vote
2answers
76 views

L ={ $a^{m^n}$ | $m$>$n$ } is Regular or not by pumping Lemma [duplicate]

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 ...
1
vote
0answers
166 views

Is the complement of this language Context-Free $\{(a^nb^n)^m \mid n>0,m>0\}$?

I've been asked to decide whether a given language is a Context-Free Language (CFL). If yes, I should find the grammar that creates her, and if not, I need to prove it (with the pumping lemma). The ...
2
votes
1answer
81 views

Help on using the pumping lemma?

I'm trying to prove that a language is not regular. That language is: {w ∈ {a, b}* | amount of a's in w is equivalent to the amount of b's in w, mod 2}. I have an inkling that this language is not ...
1
vote
1answer
66 views

Applying the context-free pumping lemma to a language with crossed nestings

For proving language $\{a^nb^mc^nd^m \mid n,m > 0\}$ is not context free. Do I have to use $z = a^pb^pc^pd^p$ as pumping lemma string where $p$ is pumping length? Or do I have to use a string that ...
1
vote
1answer
77 views

When using the Pumping lemma, how do I deal with different cases of y?

I want to prove L is not regular:$$L={\{www|w \in \Sigma^*\}}$$ $$\Sigma=\{a,b\}$$ I am sure I can do so using pumping lemma. I used $$ab^pab^pab^p$$as my chosen string but I am stuck. I do not know ...
2
votes
1answer
45 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
125 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
81 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
123 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
62 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
vote
2answers
109 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
187 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
167 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 ...
3
votes
1answer
170 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
395 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
124 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
69 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
57 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
134 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 ...