** Formal Languages And Automation Theory MCQs **

**Set IV**

**Q1. Which of the given are correct? **

**a)** Moore machine has 6-tuples

**b)** Mealy machine has 6-tuples

**c)** Both Mealy and Moore has 6-tuples ✔

**d)** None of the mentioned

**Answer is c)** Both Mealy and Moore has 6-tuples **Explanation : **The six tuples are (Q, ∑, O, Î´, X, q0)

It can be described by a 6 tuple (Q, ∑, O, Î´, X, q0) where −

Q is a finite set of states.

∑ is a finite set of symbols called the input alphabet.

O is a finite set of symbols called the output alphabet.

Î´ is the input transition function

X is the output transition function

q0 is the initial state from where any input is processed (q0 ∈ Q).

**Q2. Which of the following does not belong to input alphabet if S={a, b}* for any language?**

**a)** a

**b)** b

**c)** e ✔

**d)** none of the above

**Answer is c)** e **Explanation : ** The automaton may be allowed to change its state without reading the input symbol using epsilon but this does not mean that epsilon has become an input symbol. On the contrary, one assumes that the symbol epsilon does not belong to any alphabet.

**Q3. Design a NFA for the language:
L: {an| n is even or divisible by 3}
Which of the following methods can be used to simulate the same. **

**a)** e-NFA

**b)** Power Construction Method

**c)** Both (a) and (b) ✔

**d)** None of the mentioned

**Answer is c)** Both (a) and (b) **Explanation : ** It is more convenient to simulate a machine using e-NFA else the method of Power Construction is used from the union-closure of DFA’s.

**Q4. State true or false:
Statement: Both NFA and e-NFA recognize exactly the same languages. **

**a)** true ✔

**b)** false

**Answer is a)** true**Explanation : ** e-NFA do come up with a convenient feature but nothing new.They do not extend the class of languages that can be represented.

**Q5. The number of elements present in the e-closure(f2) in the given diagram:
**

**a)** 0

**b)** 1

**c)** 2 ✔

**d)** 3

**Answer is c)** 2 **Explanation : **The epsilon closure set of f2 consist of the elements:{f2, f3}. Thus the count of the element in the closure set is 2.

**Q6. To describe the complement of a language, it is very important to describe the __________ of that language over which the language is defined.**

**a)** Alphabet ✔

**b)** Regular Expression

**c)** String

**d)** Word

**Answer is a)** Alphabet **Explanation : ** For explanation Join the discussion below

**Q7. Which of the following not an example Bounded Information?
**

**a)** fan switch outputs {on, off}

**b)** electricity meter reading ✔

**c)** colour of the traffic light at the moment

**d)** none of the mentioned

**Answer is b)** electricity meter reading **Explanation : ** Bounded information refers to one whose output is limited and it cannot be said what were the recorded outputs previously until memorized

**Q8. How many languages are over the alphabet R?**

**a)** countably infinite

**b)** countably finite

**c)** uncountable finite

**d)** uncountable infinite ✔

**Answer is d)** uncountable infinite **Explanation : ** A language over an alphabet R is a set of string over A which is uncountable and infinite

**Q9. The number of tuples in an extended Non Deterministic Finite Automaton: **

**a)** 5 ✔

**b)** 6

**c)** 7

**d)** 4

**Answer is a)** 5 **Explanation : **For NFA or extended tranisition function NFA , the tuple of elements remains same i.e. 5

**Q10. Under which of the following operation, NFA is not closed?**

**a)** Negation

**b)** Kleene

**c)** Concatenation

**d)** None of the mentioned ✔

**Answer is d)** None of the mentioned **Explanation : ** NFA is said to be closed under the following operations:

a) Union

b) Interaction

c) Concatenation

d) Kleene

e) Negation

**Q11. Given Language: {x | it is divisible by 3}
The total number of final states to be assumed in order to pass the number constituting {0, 1} is **

**a)** 0

**b)** 1

**c)** 2 ✔

**d)** 3

**Answer is c)** 2**Explanation : **The DFA of a given language can be created

**Q12. The automaton which allows transformation to a new state without consuming any input symbols: **

**a)** NFA

**b)** DFA

**c)** NFA-I ✔

**d)** All of the mentioned

**Answer is c)** NFA-I **Explanation : **NFA-I or e-NFA is an extension of Non detrministic Finite Automata which are usually called NFA with epsilon moves or lambda transitions

**Q13. Definition of a language L with alphabet {a} is given as following. L= { ank | k > 0, and n is a positive integer constant} What is the minimum number of states needed in a DFA to recognize L?
**

**a)** k+1

**b)** n+1 ✔

**c)** 2n+1

**d)** 2k+1

**Answer is b)** n+1 **Explanation : **Note that n is a constant and k is any positive integer. For example, if n is given as 3, then the DFA must be able to accept 3a, 6a, 9a, 12a, .. To build such a DFA, we need 4 states.

**Q14. Design a NFA for the language:
L: {an| n is even or divisible by 3}
Which of the following methods can be used to simulate the same.**

**a)** e-NFA

**b)** Power Construction Method

**c)** Both (a) and (b) ✔

**d)** None of the mentioned

**Answer is c)** Both (a) and (b) **Explanation : ** It is more convenient to simulate a machine using e-NFA else the method of Power Construction is used from the union-closure of DFA’s.

**Q15. Which of the following does the given Mealy machine represents? **

**a)** 9’s Complement

**b)** 2’s Complement

**c)** 1’s Complement ✔

**d)** 10’s Complement

**Answer is c)** 1’s Complement **Explanation : ** Inputs can be taken and can be verified.

**If you have any doubts join the discussion below ,our Moderator will reply to your Queries**

#### Recommended MCQs

Formal Languages And Automation Theory MCQs With Answers - Set I

Formal Languages And Automation Theory MCQs With Answers - Set II

Formal Languages And Automation Theory MCQs With Answers - Set III

Formal Languages And Automation Theory MCQs With Answers - Set V

Formal Languages And Automation Theory MCQs With Answers - Set VI

Formal Languages And Automation Theory MCQs With Answers - Set VII

Java MCQs with Answers Set III

Informatica MCQs with Answers Set I

Informatica MCQs with Answers Set II

Informatica MCQs with Answers Set III

Informatica MCQs with Answers Set IV

Informatica MCQs with Answers Set V

Informatica MCQs with Answers Set VI

Computer Organization and Architecture MCQs with Answers Set I

Computer Organization and Architecture MCQs with Answers Set II

Computer Organization and Architecture MCQs with Answers Set III