Question

Consider the following languages

L1 = { 0^p 1^q 0^r | p,q,r >=0 }
L2 = { 0^p 1^q 0^r | p,q,r >=0, p != r }

Determine whether they are regular or context-free.

Answer 1

Answer on Question#38197 - Math - Other

$L_{1} = \{0^{p}1^{q}0^{r}|p,q,r\geq 0\}$ is regular:

$L_{2} = \{0^{p}1^{q}0^{r}|p,q,r\geq 0,p\neq r\}$ is context-free language. We can accept or reject $L_{2}$ with single stack, insert $p$ $0^{\prime}s$ into stack skip $1^{\prime}s$ . For each 0 corresponding to $r$ , remove 0 from stack.