Linked Questions

0
votes
0answers
58 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
13 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 : $...
0
votes
0answers
13 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
0answers
10 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
0answers
125 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 ...
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
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
67 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 ...
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 ...
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
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
18 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
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 ...
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