Linked Questions

0
votes
0answers
84 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 ...
1
vote
0answers
81 views

Is $\{a^mb^nc^{mn}\mid m>n\}$ a context-free language? [duplicate]

Been trying to figure it out for an hour myself and another hour looking around, I cannot find anything with the $c^{mn}$ part. $$L=\{a^mb^nc^{mn}\mid m>n\}$$
0
votes
0answers
66 views

Context-free Language, Pumping lemma [duplicate]

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 ...
0
votes
0answers
60 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
56 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 ...
0
votes
0answers
49 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 ...
-1
votes
1answer
52 views

using pumping lemma prove this language is not a context-free-language [duplicate]

How can one prove that the language below is not context-free using the pumping lemma? $$\{ a^i b^m a^j b^m a^k b^m \mid i,j,k,m \geq 0 \}$$
0
votes
1answer
37 views

Is the language $L = \{a^pb^q \ | \ p \ge 1, \ q \ge 1, \ p \ge q^2 \ or \ q \ge p^2\}$ context free? [duplicate]

Is the language $L = \{a^pb^q \ | \ p \ge 1, \ q \ge 1, \ p \ge q^2 \ or \ q \ge p^2\}$ context free? I should probably use Ogden's lemma, but I don't know how to do that in this case.
0
votes
1answer
35 views

Prove or disprove if L is CFL? [duplicate]

Given $L=\{a^ib^jc^k | i\neq j \space and \space j=k\}$. Is this CFL? How do I write CFG for it or prove it with pumping lemma? Thanks.
2
votes
0answers
33 views

For $\sum = \{ 0,1 \}$, $A$ has strings which contain a $1$ in their middle third, and a $B$ which contain two $1$'s in their middle third [duplicate]

Language $A$ can also be represented as, $$A = \{ uvw \mid u,w \in \Sigma^*\text{ and, }v \in \Sigma^* 1 \Sigma^*\text{ and, }|u| = |w| \ge |v| \}$$ Language $B$ can also be represented as, $$B = \{ ...
0
votes
0answers
28 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
0answers
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 ...
0
votes
0answers
24 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
0answers
23 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 ...
0
votes
0answers
22 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} ...

15 30 50 per page