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

learn more… | top users | synonyms

1
vote
1answer
70 views

Show language is not regular

Show that the following languages are not regular in two ways: first by using closure properties then by using the Pumping lemma: $$\text{(1) L1} = {a^n b^k c^{n+k} : n >= 0; k >= 0}$$ ...
2
votes
3answers
56 views

Proof that whether a regular language is finite is decidable

I have this question for a homework. The question stems from the fact that you can determine whether a regular language is empty by using a Turing machine to count the states n in the given FSM. When ...
0
votes
1answer
30 views

Prove using pumping free lemma for context-free languages

One of the exercises I tried to make I failed miserably. The question was as follows: Show that the language $L = \{ w \,|\, n_a(w) \cdot n_b(w) = n_c(w) \}$ is not context-free. (with $n_a(w)$ ...
-1
votes
0answers
25 views

If a CFG has a word with length more than its variables then the language of it is infinite?

Grammar G have n variables in normal Chomsky form, It can build a word with length w, using m rules. Which disprove each of following statements: If w > n then the language of the grammar G is ...
2
votes
1answer
48 views

How to pick w for the Pumping lemma if the language has no clear pattern?

I'm trying to understanding using the pumping lemma to prove that a language is not regular. I sort of understand how it works when the language describes strings with a particular form, like in this ...
0
votes
2answers
52 views

Showing that a language satisfies the pumping lemma

I am wanting to show that this language fails to show that it is not context-free. So, in essence, it satisfies the pumping lemma If L = {ambncndn | m,n >= 1 } Should I have n be the constant of the ...
0
votes
0answers
12 views

Proof by pumping lemma [duplicate]

I'm trying to use the pumping lemma proof to show that the following language is context-free rather than regular {ba^n bc^n | n ≥ 1} I've been looking at tutorials on Youtube to try and gain ...
1
vote
3answers
47 views

Misconception in taking Pumping Length of language {a} to be $2$

I would like to know why the pumping length of language {a} is $2$ as said in this chat discussion. Eventhough this discussion proves trivially that the pumping length of language {a} is $2$ I ...
-1
votes
1answer
78 views

Confusion in Pumping Lemma

I would like to know whether we could pump $ba$ into $bbba$ where x=$b$,y=a,z=$\epsilon$ using the finite state machine given in the image 1. For example as given in this image 2 where the string ...
-1
votes
1answer
33 views

Language where pumping does not work — Pumping lemma [duplicate]

I understand that the length of y must be greater than 0 but I do not understand how to show B_2 is a regular language or why pumping up does not work in part ii.
3
votes
1answer
62 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
64 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
vote
1answer
142 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
89 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
90 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
78 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
47 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
37 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
72 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
152 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
10 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
44 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
43 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
47 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
52 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
465 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
202 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
46 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
113 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
105 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
223 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
49 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
194 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
132 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
72 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
161 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
82 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
112 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
134 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
107 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
52 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
45 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
134 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
76 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
29 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
41 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
179 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
46 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 ...