general doubt toc

Question

how to draw FA for this language

$L=0^n1^m0^m:n+m\;mod\;6=0$

Answer 1

You Can't. Because this language is Not Regular.

$L = \left \{ 0^n1^m0^m | (n+m) \,\,mod\,6=2 \right \}$

Hint : Language $L$ can be seen as Intersection of Two Languages. i.e. $L = L_1 \cap L_2$ where

$L_1 = \left \{ 0^n1^m0^m | n,m \geq 0 \right \}$ 

$L_2 = \left \{ 0^i1^j0^k | (i+j) \,\,mod\,6=2; i,j,k \geq 0 \right \}$

Now, It's easy to see that $L_1$ is CFL whereas $L_2$ is Regular. And Intersection of a CFL and a Regular is Necessarily a CFL. (Refer link below)

$L$ is Non-regular  But CFL (Moreover it is DCFL because $L_1$ is DCFL and Intersection of DCFL and Regular is also DCFL.)

https://www.cs.ucsb.edu/~cappello/136/lectures/17cfls/slides.pdf