Linked Questions
114 questions linked to/from How to prove that a language is not context-free?
0
votes
0
answers
170
views
Is this language context-free? $\Sigma$ = {a,b,#} L = {x1#x2#...#xk : k$\geq$2, every $x_i \in$ {a,b}* and xi $\neq$ xj for every pair i $\neq$ j} [duplicate]
Is this language context-free? $\Sigma$ = {a,b,#}, L = {x1#x2#...#xk : k$\geq$2, every $x_i \in$ {a,b}* and xi $\neq$ xj for every pair i $\neq$ j} I think it is not, because the PDA can't memorize ...
- 21
0
votes
0
answers
15
views
Non-context free languages with word degree [duplicate]
I have stumbled across these 2 problems
$L_1= \{\alpha \mid w \in \{a,b\}^* | \alpha $ has exactly 2 b's$\} $ ,prove that $L =\{ \alpha^n | \alpha ∈ L_1 ,n \ge 0 \}$ is not context free
Given : $...
- 1
0
votes
0
answers
16
views
How do we determine p (pumping length) in pumping lemma for CFL? [duplicate]
This has been confusing me for a while, how do we exactly choose the pumping length when we want to prove whether a language is CFL or not. For example, when we want to prove that {ww, w: {0,1}* } why ...
0
votes
0
answers
13
views
Choose a specific regular language to prove a language is not regular [duplicate]
I've tried a few tricky languages such as D = { w | w has an equal number of occurences of 01 and 10 as substrings} but I don't have the means to prove this one as being not regular (and I cannot ...
0
votes
0
answers
222
views
How to show that a language is strictly context sensitive
During a class, we was asked how to prove that a language L is strictly context-sensitive. In particular, we have to prove that
$L = \{a^nb^nc^n \mid n > 0\}$
Could you help me to find the ...
- 175
0
votes
0
answers
27
views
Is this language a context-free language? [duplicate]
I'm currently trying to figure out whether this language is context-free using the pumping lemma.
$\qquad L = \{ v_1 v_2 v_1 v_2 \mid v_1 \in \{a, b\}^*, v_2 \in \{a, c\}^* \}$
I'm having trouble ...
- 3
0
votes
0
answers
29
views
Generate a Grammar from a language(Non-CFL) [duplicate]
I tried to solve this question,
We have this Language, L(g)={AA|A={0+1}*}
The output(Productions) must be similar as these = {(11 11), (0 0), (1101 1101), etc..} The left side equal to right side..
...
0
votes
0
answers
123
views
Showing $L=\{a^ib^jc^k: i,j,k \text{ not all equal}\}$ is a CFL a lemma [duplicate]
In their answer, Janoma proves that $\{a^ib^jc^k:i\neq j,j\neq k,i\neq k\}$ is not context-free using Ogden's lemma, but I haven't learned about Ogden's lemma yet. I wanted to know whether Ogden's ...
- 31
0
votes
0
answers
88
views
Proving that $L = \{a^m b^n | m \% n = 0 \}$ is not context-free [duplicate]
For language $L = \{a^m\, b^n\: |\: m \:\%\: n = 0 \}$, that is, $m$ is a multiple of $n$, I'm trying to find a proof that it isn't a context free. I know it isn't regular, but it also doesn't seem to ...
- 179
0
votes
0
answers
25
views
CFG. Ensure that $n\neq m$ twice in $L=\{a^m b^n c^m d^n, m\neq n\}$ [duplicate]
During the formal language exam, the professor allowed to find a CFG to following language: $\{a^m b^n c^p d^q, m\neq n\wedge p\neq q\}(1)$, because neither he saw a solution (He passed a test without ...
0
votes
0
answers
24
views
Prove this language is not CFL [duplicate]
I have this language: $L = \{a^{n+2} b^m a^{2n} b^{3n}\mid n,m >=0 \}$ and I am trying to prove that it is not CFL.
I assumed that my word is $a^{p+2} b^m a^{2p} b^{3p}$ (where $p$ is the pumpung ...
- 31
0
votes
0
answers
63
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
0
answers
19
views
Pumping Lemma for CFG - How to do it? [duplicate]
I'm literally so confused on how to even start this problem of proving that the given language is not Context Free.
L = {a^i b^j c^k d^l | i = k and j = l}
I ...
0
votes
0
answers
51
views
Why is this language is not context-free? [duplicate]
Anyone could apply some theorem to prove this is not context free? I read lot's of material. it's not homework, it's not exam, it's not anythings. I want to learn, if some people try to answer this ...
0
votes
0
answers
29
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}
...
user7233