Linked Questions

-1
votes
1answer
64 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
213 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 | ...
-3
votes
1answer
134 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
1k 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