Automata Theory Questions and Answers – Reversal-Homomorphism and Inverse Homomorphism

«
»

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Reversal-Homomorphism and Inverse Homomorphism”.

1. If L is a language, the reversal of the language can be represented as:
a) L’
b) Lc
c) Lr
d) more than one option is correct
View Answer

Answer: c
Explanation: Lr is defined as the reversal of a language. Lr is a set of strings whose reversal is in L.
Example: L={0, 01, 100}
Lr={0, 10, 001}
advertisement

2. If L is a regular language, ____ is also regular.
a) Lr
b) L’
c) L*
d) All of the mentioned
View Answer

Answer: d
Explanation: Lr, L’, L* i.e. reversal, complementation and kleene all are the closure properties of regular language.

3. If E=F+G;
Er=?
a) Fr+Gr
b) (F+G)r
c) Fr+Gr and (F+G)r
d) None of the mentioned
View Answer

Answer: a
Explanation: If E is a symbol a, e, or f, then Er=E. Other inductive properties include union of reversals, concatenation and Kleene.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement

4. If E= FG, Er=?
a) FrGr
b) GrFr
c) FrGr and GrFr
d) None of the mentioned
View Answer

Answer: b
Explanation: If E= FG, Er=GrFr . Example: (01*)R=(1*)R(0)R

5. Simplify the following identity:
E=01*+10*
ER=?
a) (1*0+0*1)
b) (01*10*)R
c) (0*1+10*)
d) All of the mentioned
View Answer

Answer: a
Explanation: 01*+10*
ER=(01*)R+(10*)R=>(1*)R0R+(0*)R1R=>1*0+0*1
advertisement

6. Which of the following obey the closure properties of Regular language?
a) Homomorphism
b) Inverse Homomorphism
c) Reversal
d) All of the mentioned
View Answer

Answer: d
Explanation: Homomorphism on an aphabet is a function that gives a string for each symbol in that alphabet. Example: h(0)=ab, etc.

7. Let h(L) be a language of regular expression abe*+e(ab)*. Simplify the h(L)
a) (ab)*+eab*
b) abe*+ea*b*
c) (ab)*
d) None of the mentioned
View Answer

Answer: c
Explanation: abe*+e(ab)*(Using the identities e=e*, eE=Ee=E)
=ab+(ab)*=> ab will contain inside (ab)*, thus =>(ab)*.
advertisement

8. Let h(0)=ab; h(1)=e
Let L={abab,baba}
h-1(L)=_______
a) the language of two one’s and any number of zeroes
b) the language of two zeroes and any number of one’s
c) the language of two zeroes and two one’s
d) none of the mentioned
View Answer

Answer: b
Explanation: h-1(L) is the language with two 0’s and any number of 1’s=>(1*01*01*).

9. While proving Inverse Homomorphism, which of the following steps are needed?
a) Start with a DFA Ain L
b) Construct a DFA B for h-1(L)
c) The set of states, initial and final states should be same.
d) All of the mentioned
View Answer

Answer: d
Explanation: While constructing DFA B, we need to take care of the following:
a) The same set of states
b) The same start state
c) The same final state
d) Input alphabet = the symbols to which homomorphism h applies.
advertisement

10. 8. Let h(0)=ab; h(1)=e
Let L={abab,baba}
h-1(L)= the language of two zeroes and any number of one’s.
The given example belongs to which of the following?
a) Homomorphism
b) Inverse Homomorphism
c) Homomorphism and Inverse Homomorphism
d) None of the mentioned
View Answer

Answer: b
Explanation: Let h be a homomorphism and L a language whose alphabet is the output language of h.
h-1(L) = {w | h(w) is in L}.

Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory, here is complete set of 1000+ Multiple Choice Questions and Answers.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.