I was thinking about whether $\{ 0^{a}10^{a}10^{a}|a\in\mathbb{N} \}$ is a context-free language, and I found this post. I am not sure if my understanding is correct or not, but I guess $R = \{ (a,1,a,1,a)|a\in\mathbb{N} \}$ is not a stratified set, so this language is not context-free?

Before looking this up, I have been wondering if $L =\{ 0^{a}10^{b}10^{c} |(a,b,c)\in R\}$ is context free, and my intuition is that for $(a_{0},b_{0},c_{0}) \in R$, if we modify $a_{0}$ to $a_{1} \neq a_{0}$, we must modify both $b_{0}$ and $c_{0}$ to $b_{1}\neq b_{0}$, and $c_{1}\neq c_{0}$, so that $(a_{1},b_{1},c_{1}) \in R$, then it is not context free. In other words, if we change one of a,b,c we must change the other two (not only one), for the changed 3-tuple to be in $R$, then it must not be context-free. Is my intuition correct?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.