Consider the set of all words over the alphabe...

Consider the set of all words over the alphabet {x, y, z} where the number of y’s is not divisible by 2 or 7 and no x appears after a z. This language is:

(A) regular

(B) not known to be regular 

(C) context-free but not regular 

(D) recursively enumerable but not context-free

Hint: 

<div class="tex2jax"></div>

1Comment
sumitverma's picture
Sumit Verma @sumitverma 1 Dec 2016 03:32 pm

Let Σ = {x, y, z}. The language in question is (Σ* \ (L1 ∪ L2)) ∩ L3 where
L1 = {w ∈ Σ* | the number of y’s is divisible by 2},
L2 = {w ∈ Σ* | the number of y’s is divisible by 7}
and L3 = {w ∈ Σ* | no x appears after a z}
It suffices to show that all these three languages are regular, and appeal to the fact that regular languages are closed under boolean operations.
They are described by the following regular expressions, respectively
r1 = ((x + z)* y(x + z)* y(x + z)* )*
r2 = ((x + z)* y(x + z)* y(x + z)* y(x + z)* y(x + z)* y(x + z)* y(x + z)* y(x + z)* )*
r3 = (x + y)* (y + z)*