Question

L= {x^a y^b z^c | c=a+b(mod 2)} .Create a DFA and NFA for the language L. Solution and explanation please..

Answer 1

Any DFA that accepts the given language must satisfy the following:

If a string is not of the form then it must be rejected;

If then must be rejected.

We define a DFA keeping these in view. The DFA is where

with denoting (respectively) the start state and the set of final states. The transition function is as follows:

Explanation: To understand the DFA just defined, note that the states denoted by pairs, for example , indicates that the machine has by now seen no , it has seen a string of the form , and that . So the second counter basically keeps track of , and the machine keeps being in one of these states as long as the string it has already seen is of the form . And as soon as the machine sees a string that is not of this form, it moves to the "reject" state .

Proof of the fact that the machine accepts .

As explained above, when the machine sees a string that is not of the form , it moves to reject state . If a machine sees a string then it ends up being in or according as , respectively. Thus, the machine ends in the unique final state if and only if . But if and only if . Since , this is equivalent to .

Hence, the machine accepts a string if and only if it is of the form with . Therefore, the DFA we constructed, , accepts .

Since DFA is NFA, we have constructed an NFA also, namely, itself.