1. An informal Englishdescription of the main ideas behind your solution 2. A ma

Question

1. An informal Englishdescription of the main ideas behind your solution
2. A mathematical description of all components of automatonM (See hint below.)
3. A proof that L(M) = even(L(M)) [ Hint: Your solutionmay start as follows: Let L be an arbitrary regular language. Bydefinition of regular
language, there exists a deterministic finite state automaton M =(Q,, , s, F) such that L(M) = A. We
use the components of M to build a new non-deterministic finitestate automaton M = (Q,, ,s, F)
with o-transitions such that L(M) = even(A) . . . . . . .Since M can be transformed into an equivalent
deterministic finite automaton using the method studied in class,the language even(A) is regular. ]

Explanation / Answer

Dear,    Let L be an arbitrary regular language,which is generated by some DFA, M(Q,, , s, F) such thatL(M) = A,    That means the language generated by thefinite state machine M is A.    Now, let us define an NDFA, M' such that M'= (Q,, , s, F), such thatL(M') = Even(A).    That means the machine M' generates the even(A)strings.    We know that if language is accepted by NDFAthen there exists a DFA that accepts the same language, Thus, wecan convert NDFA to DFA.     Since, the DFA, M generates a regularlanguage L(A) and the M' also defined on same language of evenstrings i.e., even(A).       For a DFA, M thatgenerates L(A) is regular and so there exists an NDFA thatgenerrates even(A) is also regular.       i.e,. L(M') = even(L(M))    " I hope this will help you "

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---