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.
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 ...
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 | ...
### 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 ...