Question

Provide direct answers. This question has been posted here by someone else before, but the answer is unreadable and does not indicate clearly the answer.

DO C.

Let Lodd = {w ∈ {0, 1}∗ | w contains an odd number of 0s}.

a) - What is L∗odd? (arrive at a direct description of this language that does not refer to Lodd).

b) Then Start with a DFA recognizing Lodd, and use the construction we saw in class to obtain an NFA recognizing L∗odd (Do not attempt to optimize the NFA or build your own DFA/NFA for the language – just apply the construction we saw in class when we proved regular languages are closed under the star operation).

c) After that, For the NFA you constructed above, show the computation trees for the strings 100 and 11 (you may omit branches that die before they reach the end of the input). Determine whether each of these strings is in L∗odd or not.

Answer 1

a) L*odd : The language is recognise by Lodd is that not containing even numbers of zero's over the input alphabet {0,1}.

and the strings would be like this :

{ 1,10,01,110,101010,1111110, ...... }

b) DFA for this language is given below :

c) The string 100 and 11 are unreachable to the final state , these strings are dies in the first state of the DFA before reaching the final state . because these strings are containing the even number of zeros .

thanks and i hope this will help you.. ?