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

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)*