Automata Theory Questions and Answers – Finding Patterns in Text,Algebric Laws and Derivatives

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Finding Patterns in Text,Algebric Laws and Derivatives”.

1. The minimum length of a string {0,1}* not in the language corresponding to the given regular expression:
(0*+1*)(0*+1*)(0*+1*)
a) 3
b) 4
c) 5
d) 6
View Answer

Answer: b
Explanation: 0101 or 1010 the strings with minimum length on {0,1}* which does not belong to the language of the given regular expression.Other strings like 111, 000, 1101, etc are accepted by the language .

2. Which of the following regular expression is equivalent to R(1,0)?
R(1,0)={111*}*
a) (11+111)*
b) (111+1111)*
c) (111+11*)*
d) All of the mentioned
View Answer

Answer: a
Explanation: What we observe from the question is that, it includes e and 11 and any number of 1’s then. Therefore, its simplifies when we write the same reg. Expression as (11+111)*.

3. The minimum number of 1’s to be used in a regular expression of the given language:
R(x): The language of all strings containing exactly 2 zeroes.
a) 2
b) 3
c) 0
d) 1
View Answer

Answer: b
Explanation: It is not required to automate the question if asked theoretically.The number of zeroes fixed is 2. Therefore, we can represent the regular expression as 1*01*01*.
advertisement
advertisement

4. The given regular language corresponds to which of the given regular language
e+1+(1+0)*0+(0+1)*11
a) The language of all strings that end with 11 or 00
b) The language of all strings that end with 0 or 1
c) The language of all strings which does not end with 01
d) None of the mentioned
View Answer

Answer: c
Explanation: According to the given regular expression, e is accepted by its language and it does not end with 00 or 11 or 0 or 1. Thus option a and b are eliminated. Further, the regular expression is valid for the third option.

5. Statement: If we take the union of two identical expression, we can replace them by one copy of the expression.
Which of the following is a correct option for the given statement?
a) Absorption Law
b) Idempotent Law
c) Closure Law
d) Commutative Law
View Answer

Answer: b
Explanation: Idempotent Law states that if we take the union of two like expression, we can use a copy of the expression instead i.e. L+L=L. The common arithmetic operators are not idempotent.

6. Which among the following can be an annihilator for multiplication operation?
a) 0
b) 1
c) 100
d) 22/7
View Answer

Answer: a
Explanation: An annihilator for an operator is a value such that when the operator is applied to the annihilator and some other value, the result is the annihilator.

7. Statement: A digit, when used in the CFG notation, will always be used as a terminal.
State true or false?
a) True
b) False
View Answer

Answer: a
Explanation: Lowercase letters near the beginning of an alphabet, a, b and so on are terminal symbols. We shall also assume that digits and other characters such as + or parenthesis are terminals.
advertisement

8. Choose the incorrect process to check whether the string belongs to the language of certain variable or not?
a) recursive inference
b) derivations
c) head to body method
d) All of the mentioned
View Answer

Answer: d
Explanation: There are two approaches to infer that certain string are in the language of a certain variable. The most conventional way is to use the rules from body to head, recursive inference. The second approach is expanding the starting variable using one of its productions whose head is tart symbol and derive a string consisting entirely of terminals(head to body or derivations).

9. Statement: Left most derivations are lengthy as compared to Right most derivations.
Choose the correct option:
a) correct statement
b) incorrect statement
c) may or may not be correct
d) depends on the language of the grammar
View Answer

Answer: c
Explanation: It completely depends on the person who develops the grammar of any language, how to make use of the tools i.e. leftmost and rightmost derivations.
advertisement

10. A->aAa|bAb|a|b|e
Which among the following is the correct option for the given production?
a) Left most derivation
b) Right most derivation
c) Recursive Inference
d) None of the mentioned
View Answer

Answer: a
Explanation: The given form represents leftmost derivations in which at each step we replace the leftmost variable by one of its production bodies.
The given form represents leftmost derivations of production bodies

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.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

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 & discussions at Telegram SanfoundryClasses.