Question

Need help with this question. Thank you!

Problem 146. Give an algorithm for the following decision problem. DFA AcceptNoOdd INPUT: A DFAM QUESTION: Does M accept no odd-length strings? This is the same as asking, when D is the set of all odd-length strings, whether L( MD=0.

Answer 1

Here is a simple Solution for the Problem:

1:Create a DFA, NN that accepts only odd-length strings (a two-state DFA will do it).

2:On input MM, determine whether L(M)=L(N)L(M)=L(N), using known results about regular language closure properties (for example, for any sets A,BA,B we know A=BA=B if and only if their symmetric difference, (A∩B¯¯¯¯)∪(A¯¯¯¯∩B)(A∩B¯)∪(A¯∩B) is empty). If A,BA,B are regular, then their symmetric difference is regular (by closure properties of regular languages

3:Test the symmetric difference for emptiness. There's a well-known result about how to do that for regular languages.

4:If the difference is empty, answer "yes" else answer "no

********************************************Thank You************************************************************