Question

Write a grammar for a language whose sentences start with an even and non-zero number of x’s, end with an odd number of z’s, and have a number of y’s in between equal to the total number of x’s and z’s in the sentence. For example, xxyyyyyzzz is a valid sentence.

Answer 1

GRAMMAR

S -> AB

A -> xxAyy | xxyy

B -> yyBzz | yz

EXPLANATION

A is for even number of x's followed by that number of y's

B is for odd number of y's followed by that number of z's