Formal Languages And Automation Theory MCQs With Answers - 2

Formal Languages And Automation Theory MCQs With Answers - 2

Q1. In Moore machine, output is produced over the change of:

a) transitions

b) states ✔

c) Both

d) None of the mentioned

Answer is b) states
Explanation : Moore machine produces an output over the change of transition states while mealy machine does it so for transitions itself.

Q2. Number of states require to accept string ends with 101.

a) 3

b) 4 ✔

c) 2

d) can’t be represented

Answer is b) 4
Explanation : For explanation Join the discussion below

 

Q3. Given the language L = {ab, aa, baa}, which of the following strings are in L*?
1) abaabaaabaa
2) aaaabaaaa
3) baaaaabaaaab
4) baaaaabaa

a) 1, 2 and 3

b) 2, 3 and 4

c) 1, 2 and 4 ✔

d) 1, 3 and 4

Answer is c) 1, 2 and 4
Explanation : Any combination of strings in set {ab, aa, baa} will be in L*.
1) “abaabaaabaa” can be partitioned as a combination of strings in set {ab, aa, baa}. The partitions are “ab aa baa ab aa”
2)“aaaabaaaa” can be partitioned as a combination of strings in set {ab, aa, baa}. The partitions are “aa ab aa aa”
3)“baaaaabaaaab” cannot be partitioned as a combination of strings in set {ab, aa, baa}
4)“baaaaabaa” can be partitioned as a combination of strings in set {ab, aa, baa}. The partitions are “baa aa ab aa”

 

Q4. Language of finite automata is generated by

a) Type 0 grammar

b) Type 1 grammar

c) Type 2 grammar

d) Type 3 grammar ✔

Answer is d) Type 3 grammar
Explanation : The equivalence of regular expressions and finite automata is known as Kleene's theorem (after American mathematician Stephen Cole Kleene). In the Chomsky hierarchy, regular languages are defined to be the languages that are generated by Type-3 grammars (regular grammars).

 

Q5. Which of the following are the examples of finite state machine system?

a) Control Mechanism of an elevator, Traffic Lights

b) Combinational Locks

c) Digital Watches

d) Both a & b ✔

Answer is d) Both a & b
Explanation : Control Mechanism of an elevator, Traffic Lights and Combinational Locks are finite state machine

 

Q6. Moore Machine is an application of:

a) Finite automata without input

b) Finite automata with output ✔

c) Non- Finite automata with output

d) None of the mentioned

Answer is b) Finite automata with output
Explanation : Finite automaton with an output is categorized in two parts: Moore M/C and Mealy M/C.

 

Q7. The total number of states and transitions required to form a moore machine that will produce residue mod 3.

a) 3 and 6 ✔

b) 3 and 5

c) 2 and 4

d) 2 and 5

Answer is a) 3 and 6
Explanation : For explanation Join the discussion below

 

Q8. What is the complement of the language accepted by the NFA shown below? Assume ∑ = {a} and ε is the empty string

a) Φ

b) ε ✔

c) a

d) {a, ε}

Answer is b) ε
Explanation : The given alphabet ∑ contains only one symbol {a} and the given NFA accepts all strings with any number of occurrences of ‘a’. In other words, the NFA accepts a+. Therefore complement of the language accepted by automata is empty string.

 

Q9. The finite automata is called NFA when there exists____________ for a specific input from current state to next state

a) Single path

b) Multiple paths ✔

c) Only two paths

d) None

Answer is b) Multiple paths
Explanation : For explanation Join the discussion below

 

Q10. Transition function of NFA machine is given by.

a) Σ x Q -> Σ

b) Q x Σ -> Σ

c) Q x Σ -> Q

d) Q x Σ -> 2 power Q ✔

Answer is d) Q x Σ -> 2 power Q
Explanation : For explanation Join the discussion below

 

Q11. The output alphabet can be represented as:

a) δ

b) ∆ ✔

c) ∑

d) None of the mentioned

Answer is b) ∆
Explanation : Source-The tuple definition of Moore and mealy machine comprises one new member i.e. output alphabet as these are finite machines with output.

 

Q12. ε-closure of state is combination of self state and ________________

a) ε-reachable state ✔

b) initial state

c) Final state

d) All

Answer is a) ε-reachable state
Explanation : For explanation Join the discussion below

 

Q13. The O/P of Moore machine can be represented in the following format:

a) Op(t)=δ(Op(t))

b) Op(t)=δ(Op(t)i(t)) ✔

c) Op(t):

d) None of the mentioned

Answer is a) Op(t)=δ(Op(t))
Explanation : Op(t)=δ(Op(t)) is the defined definition of how the output is received on giving a specific input to Moore machine.

 

Q14. For a give Moore Machine, Given Input=’101010’, thus the output would be of length:

a) |Input|+1 ✔

b) |Input|

c) |Input-1|

d) Cannot be predicted

Answer is a) |Input|+1
Explanation : Initial state, from which the operations begin is also initialized with a value.

 

Q15. Statement 1: Null string is accepted in Moore Machine. Statement 2: There are more than 5-Tuples in the definition of Moore Machine.
Choose the correct option:

a) Statement 1 is true and Statement 2 is true ✔

b) Statement 1 is true while Statement 2 is false

c) Statement 1 is false while Statement 2 is true

d) Statement 1 and Statement 2, both are false

Answer is a) Statement 1 is true and Statement 2 is true
Explanation : Even ε, when passed as an input to Moore machine produces an output.