Linked Questions

-1
votes
1answer
66 views

How construct PDA to $L = \{x \in(a,b,c,d)^* \mid -10 \leq ( |x|_a + |x|_b) - ( |x|_c + |x|_d) \leq 10 \}$

$L = \{x \in(a,b,c,d)^* \mid -10 \leq ( |x|_a + |x|_b) - ( |x|_c + |x|_d) \leq 10 \}$ I don't have any idea. Can someone help me.
-1
votes
1answer
219 views

Pumping lemma for {w | w = ddd}

I want to use the pumping lemma to show that the following language is not context free: $$ L = \{w \in \{a,b\}^* \mid \exists d \in \{a,b\}^*, w=ddd \} $$ We suppose that $L$ is context-free. Then ...
-1
votes
1answer
1k views

Determining whether a context-free language (CFL) described by a given grammar is regular (RL)

In my homework we're given the following problem: Determine whether the context-free language described by the following grammar is regular, showing all the reasoning steps: S -> T T | U T -> 0 T | ...
-1
votes
1answer
24 views

Is there any tiny tips to find counter example string for proving some language is not a CFL? [duplicate]

When I prove some language is context free, It is too hard to find example string. Is there any tips? It takes too many time or eventually give up.
-1
votes
1answer
55 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 \}$$
-3
votes
1answer
139 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\leqslant i\leqslant |t|$ the $i$ letter in $t$ diffrent from the $i$ letter in $s$. Prove that ...
-3
votes
2answers
2k views

Pumping Lemma for Context-Free Languages for reversal language [duplicate]

Show that the language L = {ww^Rw: w in {a,b}*} is not a context-free language.

15 30 50 per page
1
4 5 6 7
8