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.
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 ...
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 | ...
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.
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 \}$$
### 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 ...