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: 

Responses

sumitverma's picture

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

Did not found what you are looking for, Ask your doubt or Help by your contribution

Enter your search keyword:

Search form

Wait!

Here is a chance to join biggest community of technical Students,
Tutors with FREE learning resources and so much more.
It takes less then 60 seconds.