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

learn more… | top users | synonyms

3
votes
1answer
56 views

Is no language with the non-primes property context-free?

A language $L$ is said to have the "no primes" property if: For every prime $p$ there are no words $w$ in $L$ s.t. $|w|=p$. For every non-prime $m$ there is at least one word $w\in L$ of length ...
1
vote
1answer
44 views

Can $ \{A^nB^nA^nB^n \mid n \geq 0 \}$ be pumped using the pumping lemma?

In order to show that $ \{A^nB^nA^nB^n \mid n \geq 0 \}$ isn't CFL, I was trying to use a pumping lemma this way: At first we assign $w= A^jB^jA^jB^j ,$ $(w^i=uv^ixy^iz), p<|vxy|, p<j.$ if ...
-1
votes
0answers
45 views

How to prove the following language is not context-free? [duplicate]

I'm having trouble to get the whole point of the pumping lemma for CFL and how to write the proof correctly. I'll be happy to get some help to prove the following language is not a context-free: ...
1
vote
1answer
58 views

Pumping Lemma for $L = \left \{ a^{c}\mid \text{c is a composite number} \right \}$

$L = \left \{ a^{c}\mid \text{c is a composite number} \right \}$ I feel that this is not a context-free language as checking this constraint requires divisibility checking, but I am facing a hard ...
-3
votes
1answer
83 views

Showing that $\mathscr{L}$ is not context-free-grammar language

Let $"t"$ and $"s"$ be a words we will say that two words are "completly different" if for all $1\leq i\leq |t|$ the $i$ letter in $t$ diffrent from the $i$ letter in $s$. Prove that the language ...
0
votes
1answer
79 views

L=ww is not a CFL

I am studying CFL at the moment and I found this confusing. What I've just read is that, $L=\{ww\}$ is not a CFL. The proof showed it by using pumping lemma for CFL. ($w=0^n1^n0^n1^n$) and I fully ...
1
vote
1answer
66 views

Show this language is non-regular using pumping lemma: B = {ww | w ∈ {a,b,c,…,z)*} [duplicate]

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

Use the pumping lemma to prove that {www} is not context-free

Use the pumping lemma to prove that the following language is not context-free. $\qquad L = \{ w w w \mid w \in \{a,b\}^*\}$ I am studying for an exam and really trying to understand this question. ...
0
votes
0answers
33 views

How to prove that the language of words ucv with as many a's in u as b's in v is irregular?

I'm trying to prove that: $L=\{w\in\{a,b,c\}^*\Big|\#_a(u)=\#_b(v),\ \ w=ucv,\ \ \ u,v\in\{a,b\}^*\}$ is irregular, so I'm trying to use the Pumping Lemma. This is what I tried so far: ...
-1
votes
1answer
63 views

Language of Palindrome-Prefixed Words

Classify the language $L = \{xx^Rw\ \big|\ (|x| \geq 0\ \wedge |w|\gt 0)\ where\ x,w\in\Sigma^*\}$ as one of: Regular but not Context-Free Context-Free but not Regular Decidable ...
4
votes
2answers
125 views

Pumping lemma: if you can keep pumping, what does this tell you?

Hypothetically, let's say you are using the pumping lemma for either regular or context free languages. Now using either, you come across a case that remains true despite pumping it. In this ...
0
votes
0answers
9 views

Proving that a language is not regular [duplicate]

Let's say I have a language L where {w^n b^m c^n d^m | where m is greater than or equal to 0, and n is greater than or = to 0 } How can I use the pumping lemma to prove that this is not a regular ...
0
votes
1answer
33 views

Why is this language not context free?

I been watching tutorials about how to check if a language is not context-free and in 1 video there was a language: L = {a^n b^n c^n | n ≥ 0} and they used a pumping lemma to prove that it's not ...
0
votes
1answer
38 views

How to check if my language is context-free can't seem to solve it using pumping lemma

I have a language and I am trying to see if it's context-free or not, by trying to use a pumping-lemma but I can't figure it out, been reading a lot of other posts but still struggling to apply it to ...
2
votes
1answer
43 views

How to prove that $L_1=1^*\cup \{0^i 1^{j^2}|i\ge 0,j\ge 0\} $ is irregular? [duplicate]

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 ...
0
votes
3answers
51 views

Why does it seem as if I can apply the Pumping lemma to a language that is regular?

We learn about the Pumping Lemma at the class and I tried to make few examples to understand it... There I make this example: Let's say: $L=\{w\in L|w=(0+1)^*1\}$ - i.e. - L is the language of all ...
1
vote
1answer
133 views

What is the minimum pumping length of the following languages?

How to determine the minimum pumping length of union of two languages? How do I proceed after determining the individual pumping lengths? 0*1+0+1* U 10*1 - Here the minimum pumping length of the ...
3
votes
1answer
116 views

Is {ww^r ww^r} a context-free language?

Is the language $L = \{w w^r w w^r \mid w \in \Sigma^*\}$ context-free? ($w^r$ is the reversal of $w$.) I heard that by using the pumping lemma, we can only prove that a language is not context-free, ...
2
votes
1answer
44 views

If a language has any single occurrence of a letter, is it not context-free?

From what I understand, the rules for CFL from my notes say: If $L$ is a language and • for all integers $N$, • there is a string $w \in L$ of length greater than $N$ such that • for all ways of ...
2
votes
2answers
98 views

Using closure properties to show that $a^n b^m a^{n+m}$ is not regular

I want to show that $L = \{a^n b^m a^{n+m} \mid n, m \geq 0\}$ is not regular. Can I say that the complement of $L$ intersected with $a^*b^*$ equals $\{a^n b^n \mid n \geq 0\}$ and since I know that ...
2
votes
3answers
100 views

Proof that a given language is not context-free

Given the language $L = \{w \in \{a,b\}^* \, | \, |w| = n \cdot \sqrt{n} \text{ and } n \geq 42\}$ and the assignement to proof that $L \notin CFL$ with the Pumping lemma. Assuming $L \in CFL$, ...
5
votes
4answers
216 views

Proving non-regularity of $u u^R v$?

This particular language: $$L = \{ u u^R v \,:\, u, v \in \{0, 1\}^+\}$$ is giving me a lot of trouble. I highly suspect that its non-regular, considering that $\{ u u^R : u \in \{0, 1\}^+\}$ is ...
0
votes
0answers
28 views

Can somebody please explain what the pumping lemma is? [duplicate]

I've had multiple lectures on the pumping lemma but still can't grasp exactly what it is...my main questions are as follows What is the pumping lemma for? How do you use it to prove a language is ...
2
votes
1answer
32 views

'Quick' way to show non-regularity of languages that are 'close' to other non-regular langauges

Take the language $L = \{a b^n c^n \; : \; n \geq 0\}$. It's obvious that $L$ is non-regular because $\{b^n c^n \; : \; n \geq 0\}$ is non-regular, but I don't know a satisfying way to show that to ...
2
votes
1answer
42 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 ...
5
votes
1answer
148 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 ...
2
votes
1answer
104 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
70 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 ...
0
votes
1answer
158 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
81 views

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

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
97 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
104 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
104 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
51 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
44 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
92 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
64 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
26 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
39 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
140 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
45 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
97 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
67 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
95 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
45 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
31 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
68 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
48 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
86 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
34 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^*, ...