Necessary properties of formal langagues in certain classes that rely on closure against repetition of certain subwords.
6
votes
0answers
70 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 ...
4
votes
3answers
98 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
113 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
42 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 ...
10
votes
0answers
206 views
Is this strange language context free?
Is the following language context free: $L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^*\text \{ \epsilon \} \ ,\ \mid u \mid = \mid v \mid \ , \ u \not= v \ , \ \mid x \mid = \mid y \mid \ , \ x \not= y \ ...
2
votes
1answer
65 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)$ ...
2
votes
1answer
106 views
Is the language $L = \{ a^ib^j \mid i\ \nmid\ j \ \} $ context free?
Is the language $L = \{ a^ib^j \mid i\ \nmid\ j \ \} $ context free ?
If we fix $n \in N$ then we know that the language $L = \{ a^ib^j \mid \ \forall \ 1 \le k \le n \ , \ \ j\neq ki \} $ is ...
1
vote
1answer
32 views
Questions about an answer to a pumping lemma question for CFLs
In the answer to this question, I'm not understanding how the string is derived for a given $l$.
For example,
Case 1: $vx = a^i$ where $i > 0$. Choose $l = 2$ to get $a^{n+i} b^{n+1} c^{n+1} ...
1
vote
1answer
40 views
Using pumping lemma to show $L = \{a^i b^j a^k \ | \ k > i + j\}$ cannot be accepted by an FA
$L = \{a^i b^j a^k \ | \ k > i + j\}$
Use the pumping lemma to show that this language cannot be accepted by an FA.
Proof:
Suppose $L$ can be accepted by an FA.
Suppose a string $s = ...
8
votes
1answer
198 views
Is the language $\{0^n 1^m \mid n \text{ and } m \text{ are co-prime}\}$ context-free?
Is the language $ L = \{0^n 1^m \mid n \text{ and } m \text{ are co-prime}\}$ context-free ?
I guess that it's not context free because it seems too complicated for a PDA to decided whether 2 numbers ...
0
votes
0answers
15 views
Pumping Lemma on CFL Problem [duplicate]
I have laid out the various cases that would make this not a context free language already and proved all but one for this set:
\begin{equation}
A = \{a^f b^g \mid f = g^2\}
\end{equation}
...
4
votes
2answers
112 views
Why is the following language not context-free?
$L = \{a^n b^m | m \not= n^2 \}$
I guess I need to use Pumping Lemma for CFL in order to prove this. But I'm stuck.
Assuming that $ a^n b^m = uvxyz$, we know that $v$ or $y$ can not have both $a$ ...
4
votes
2answers
113 views
A pumping lemma for deterministic context-free languages?
The pumping lemma for regular languages can be used to prove that certain languages are not regular, and the pumping lemma for context-free languages (along with Ogden's lemma) can be used to prove ...
2
votes
2answers
125 views
Pumping lemma for CFG doubt
I was looking at the pumping lemma for CFG. I came across the first problem $a^nb^nc^n$ and understood the answer. Then I thought of the problem $a^nb^n$. I know that this is context free and thought ...
0
votes
1answer
59 views
How do you apply Context-Free Pumping Lemma to these problems, and how do the approaches differ? [closed]
How are these Context-Free Pumping Lemma Approaches differ?
Maybe this might help understand pumping lemma better
$(a^{i}b^{i}c^{j}d^{j} \mid i, j \geq 0$}
$(a^{i}b^{j}c^{i}d^{j} \mid i, j \geq 0$}
...
0
votes
1answer
65 views
Pumping Lemma for regular languages proof doubt - Sipser Book
I was reading the proof of pumping lemma from Sipser's book. I couldn't understand certain things mentioned there.
In the second paragraph he has written, "because $r_l$ occurs among first $p+1$ ...
0
votes
1answer
39 views
Proving a language is not regular with pumping lemma
I'm having a little bit of an issue with a pumping lemma problem. I've successfully completely all my other problems but this is the last one and I'm a little confused I must say. If anyone can help ...
3
votes
1answer
77 views
Proving that a specific language is a CFL, and that another language is not a CFL
I have two languages $C_1$ and $C_2. \left(\Sigma=\{0,1\}\right)$:
$C_1=\left\{xyz\mid x,z \in \Sigma^*, y \in \Sigma^*1\Sigma^*, \text{ where } |x|=|z| \geq |y|\right\}$, and $C_2=\left\{xyz\mid x,z ...
1
vote
1answer
109 views
How to apply the pumping lemma to $\{0^m 1^n \mid 2n \leq m \leq 3n, m,n \geq 0 \}$?
I'm not really sure the how you would go about proving this language isn't regular with the pumping lemma:
$L= \{0^m 1^n | 2n \leq m \leq 3n, m,n \geq 0 \}$
Does this indicate that $S = 2$, so we ...
3
votes
1answer
63 views
Factorial usage within proof using the pumping lemma
We are going over the pumping lemma in class and we recently went over the following example:
Let
$$ L = \{ w \mid w \text{ has a different number of 0s and 1s} \} $$
Consider
$$
s = ...
0
votes
1answer
51 views
Is pumping lemma for regular languages “closed” against Kleene star?
If I have an infinite language $L$ which fulfills the Pumping lemma for regular languages, does $L^*$ also fulfill the same conditions?
3
votes
1answer
98 views
Prove that $\{0^n 1^{n\cdot m} : n,m \in \mathbb{N}\}$ is not context-free
This is a homework problem I have spent several hours on. A "hint" is given that we may use this fact: If $n,j,k \in \mathbb{N}$ satisfy $ n \geq 2$ and $1 \leq j+k \leq n$, then $n^2+j$ does not ...
3
votes
3answers
44 views
Where do the length restrictions of the pumping lemma come from?
For a language $L$ with pumping length $p$, and a string $s\in L$, the pumping lemmas are as follows:
Regular version:
If $|s| \geq p$, then $s$ can be written as $xyz$, satisfying the following ...
3
votes
2answers
83 views
What's the reason for the second condition of the pumping lemma(s)?
For a language $L$ with pumping length $p$, and a string $s\in L$, the pumping lemmas are as follows:
Regular version:
If $|s| \geq p$, then $s$ can be written as $xyz$, satisfying the following ...
3
votes
2answers
120 views
Prove that the language of unary not-prime numbers satisfies the Pumping Lemma
Here is a question from Daniel I. A. Cohen's book Introduction to Computer Theory:
Consider the language:
$\quad \mathrm{PRIME}' = \{ a^n \mid n \text{ is not a prime} \} = \{ \varepsilon, ...
4
votes
2answers
208 views
Is this language regular or not?
$L_1=\{a^ku \mid u \in \{a,b\}^* $ and $u$ contains at least $k$ a's, for $k\geq 1\}$.
If it is regular, I haven't found its regular expression or any closure property to prove it.
If not, it seems ...
1
vote
1answer
249 views
Push down automata for $\{a^n b^n c^n | n \ge 0\}$
I am learning about context free languages.
I understand how $\{a^n b^n c^n | n \ge 0\}$ can be shown to be not context free using the pumping lemma for CFL's.
Intuitively however it seems that a ...
4
votes
1answer
70 views
What are some good hints for proving non-regularity with the pumping lemma?
My CS Theory Professor said that when proving that a language is not regular by the Pumping Lemma, that there are some 'tricks' for solving languages more complicated that something like $L = \{a^{n} ...
2
votes
1answer
62 views
Pumping lemma problem
I need some help with the following question:
One of the languages
$$L_1 = \{a^pb^{q+r}c^sd^{q+t}e^{p+r} \mid p, q, r, s \ge 0\ , s > t\}$$
$$L_2 = \{a^{p+q}b^rc^sd^{q+r}e^s \mid p, q, r, s \ge ...
1
vote
1answer
47 views
Pumping lemma problem - Choosing the right string to pump
I have a problem finding the right string to pump for the following language:
$$L_1 = \{a^{p+q}b^rc^sd^{q+r}e^s \mid p, q, r, s \ge 0\}$$
Which string should I choose to pump? The problem is that I ...
0
votes
1answer
79 views
Pumping lemma for Context-Free Languages
I have a question about a specific pumping lemma problem for Context-Free Languages.
Suppose we have the following Language:
$L = \{a^{i}b^{j}c^{k}d^{l} \mid 0 < i < k \wedge j > l > ...
6
votes
3answers
208 views
Proofs using the regular pumping lemma
I have two questions:
I consider the following language
$$L_1= \{ w\in \{0,1\}^* \mid \not \exists u\in \{0,1\}^* \colon w= uu^R\}.$$
In other words $w$ is not palindrome with even length. I proved ...
0
votes
0answers
36 views
Show that a language is not regular by Pumping Lemma [duplicate]
Possible Duplicate:
How to prove that a language is not regular?
Show that $L_2=\{a^nb^k|n\not= k-1\}$ is not regular by Pumping Lemma.
2
votes
2answers
249 views
Pumping Lemma for regular language for $a^n$ where $n$ is even fails
$$L=\{a^n \mid \text{\(n\) is even}\}$$
This is regular but fails in the pumping Lemma.
Assuming $m=4$, $w=aaaaaa$, $|w|=6$ (even).
Let $w=xyz$,
$x=a$,
$y=aaa$.
We have $|y|>0$ and $|xy| \le m$.
...
5
votes
1answer
225 views
Proof that $a^{n^2}$ is not regular
Show that $L=\{a^{n^2} | n \geq 0\}$ is not regular
Hey guys. I'm taking a CS class and this stuff is really new to me so bear with me.
I tried to look if I get some contradiction by using the ...
6
votes
1answer
192 views
Is this language Context-Free?
Is the language
$$L = \{a,b\}^* \setminus \{(a^nb^n)^n\mid n \geq1 \}$$
context-free? I believe that the answer is that it is not a CFL, but I can't prove it by Ogden's lemma or Pumping lemma.
7
votes
3answers
317 views
How to feel intuitively that a language is regular
Given a language $ L= \{a^n b^n c^n\}$, how can I say directly, without looking at production rules, that this language is not regular?
I could use pumping lemma but some guys are saying just looking ...
5
votes
3answers
117 views
Length of mid part of the string in Pumping Lemma
This standard definition of pumping lemma from Wikipedia.
Let $L$ be a regular language. Then there exists an integer $p\ge 1$ (depending only on $L$) such that every string $w$ in $L$ of length ...
1
vote
0answers
41 views
Show that a language is not regular using the Pumping Lemma [duplicate]
Possible Duplicate:
How to prove that a language is not regular?
Given a language $L = \{a^pb^{2p} \mid p \ge 1\}$, how could I show, using the Pumping Lemma that $L$ is not regular?
5
votes
2answers
528 views
Pumping lemma for simple finite regular languages
Wikipedia has the following definition of the pumping lemma for regular langauges...
Let $L$ be a regular language. Then there exists an integer $p$ ≥ 1
depending only on $L$ such that every ...
4
votes
1answer
249 views
A context free grammar proof
There is a problem which I cannot solve. If you give a tip I will be very glad.
Prove that following language is not context free:
$L= \{ a^nb^m | \gcd(n,m) = 1 \}$.
It can be proven using the ...
4
votes
3answers
546 views
Irregularity of $\{a^ib^jc^k \mid \text{if } i=1 \text{ then } j=k \}$
I read on the site on how to use the pumping lemma but still I don't what is wrong with way I'm using it for proving that the following language is not a regular language:
$L = \{a^ib^jc^k \mid ...
3
votes
1answer
91 views
Null Characters and Splitting the String in the Pumping Lemma
So I'm really struggling with the pumping lemma. I think most of my problems come from not understanding how you can and can't split the string in a pumping lemma question. Here is an example, take ...
4
votes
1answer
469 views
Prime number CFG and Pumping Lemma
So I have a problem that I'm looking over for an exam that is coming up in my Theory of Computation class. I've had a lot of problems with the pumping lemma, so I was wondering if I might be able to ...
7
votes
3answers
658 views
Using Pumping Lemma to prove language is not regular
I'm trying to use pumping lemma to prove that $L = \{(01)^m 2^m \mid m \ge0\}$ is not regular.
This is what I have so far: Assume $L$ is regular and let $p$ be the pumping length, so $w = (01)^p ...
8
votes
2answers
539 views
How can I prove this language is not context-free?
I have the following language
$\qquad \{0^i 1^j 2^k \mid 0 \leq i \leq j \leq k\}$
I am trying to determine which Chomsky language class it fits into. I can see how it could be made using a ...
3
votes
1answer
108 views
Pumping Lemma: is it valid to “multiply the product of powers” in this case?
I need to show that
$\qquad \displaystyle S = \{(10^p)^m \mid p \geq 0, m \geq 0\}$
is not a regular language using pumping lemma.
Can I multiply the product of the powers and express it to: $S = ...
