Finite State machine (NDFA & DFA) MCQ

 1. How many tuples are in finite state machine?

a) 3

b) 4

c) 5

d) infinite

Answer-c

Finite state machine is defined as 5-tuples (Q,∑,δ,q0,F)

Where

Q: finite set of states

∑: finite set of input symbol

q0: initial state

F: final state

δ: Transition function

2. Which of the following is transition function for DFA .

a) Q * Σ ->2^Q

b) Q * Q -> Σ

c) Σ * Σ -> Q

d) Q * Σ -> Q

Answer-d

Explanation-

The transition function for DFA is defined as

δ: Q x ∑ →Q  

3. How many states are required to accept string 

which ends with 10.

a) 3

b) 2

c) 1

d) 4

Answer:a

4. Which of the following is transition function for NDFA .

a) Q * Σ ->2^Q

b) Q * Q -> Σ

c) Σ * Σ -> Q

d) Q * Σ -> Q

Answer-a

The transition function for NDFA is defined as

δ: Q x ∑ →2^Q  

5. δ*(q1,xy) is equivalent to .

a) δ((q1,y),x)

b) δ(δ*(q1,x),y)

c) δ(q1,xy)

d) None of these

Answer:b

6. String w is accepted by finite automata if .

a) δ(q0,w)|-*qf

b) δ(qf,w)|-*q0

c) δ(q0,qf)|-w

d) δ(qf,q0)|-w

Answer:a

Explanation: If FA starts with starting state and after finite moves if reaches to final step then it called accepted.

7. Languages of a finite state machine is

a) If its every string  is accepted by finite state machine

b) If its last string accepted by finite state machine

c) if it halts

d) All of the above

Answer:a

Explanation: If every string  accepted by automata it is called language of automata.

8. Which of the following type of language is accepted by finite automata ?

a) Type 0

b) Type 1

c) Type 2

d) Type 3

Answer:d

Explanation: According to Chomsky hierarchy type 3 is accepted by FA.

9. How many stacks are required in Finite state machine.

a) 1

b) 0

c) 2

d) 5

Answer:b

Explanation: Finite automata doesn’t require any stack operation .

10. Number of final state require to accept Φ in minimal finite automata.

a) 1

b) 2

c) 3

d) 0

Answer:d

Explanation: No final state requires.

11. Regular expression for all strings starts with ab and ends with bba is.

a) aba*b*bba

b) ab(ab)*bba

c) ab(a+b)*bba

d) All of the mentioned

Answer:c

Explanation: Starts with ab then any number of a or b and ends with bba.

12. How many DFA’s exits with two states over input alphabet {0,1} ?

a) 16

b) 26

c) 32

d) 64

Answer:d

Explanation: Number of DFA’s = 2n * n(2*n).

13. The basic limitation of finite automata is that

a) It can’t remember arbitrary large amount of information.

b) It sometimes recognize grammar that are not regular.

c) It sometimes fails to recognize regular grammar.

d) All of the mentioned

Answer:a

Explanation:Because there is no memory associated with automata.

14. How many states are required to store ‘4’ words each of length ‘8’.

a) 4 * 28

b) 2(4*8)

c) 2(4+8)

d) None of the mentioned

Answer:b

Explanation: 2(m*n) states requires .

15.Which of the following is an application of Finite Automaton?

a) Lexical analyzer

b) Parsers

c) Text editor

d) All of the above

Answer-d

Comments

Post a Comment

Popular posts from this blog

The python program allows the user to enter the Sales amount and Actual cost of a Product. Next, Python calculates the Loss Amount or profit Amount based on those two values using if-elif-else Statement

Image
  Write Pseudocode and draw flow chart of the following problem . The python program allows the user to enter the Sales amount and Actual cost of a Product. Next, Python calculates the Loss Amount or profit Amount based on those two values using if-elif-else Statement. Answer- Pseudocode Input the Actual cost of  Product Input the Sales Amount if(actual_cost > sale_amount):     amount = actual_cost - sale_amount     print("Total Loss Amount") elif(sale_amount > actual_cost):     amount = sale_amount - actual_cost     print("Total Profit ") else:     print("No Profit No Loss!!!") Flow chart- Python Code- #Input Actual cost of  Product actual_cost = float(input(" Please Enter the Actual cost of  Product:")) # Input Sales Amount sale_amount = float(input(" Please Enter the Sales Amount: ")) #calculate Loss Amount if(actual_cost > sale_amount):     amount = actual_cost - sale_amount     print(...
Read more

Mealy and Moore Machine

 Mealy Machine – A mealy machine is defined as 6 tuples (Q, q0, ∑, Δ, δ, λ’)  Q - finite non empty set of states  q0 - initial state  ∑-  input alphabet or terminals  Δ - output alphabet  δ - transition function δ:Q×∑ → Q  λ - output function λ: Q×∑→ O  Moore Machine – A moore machine is defined as 6 tuples (Q, q0, ∑, Δ, δ, λ’)  Q - finite non empty set of states  q0 - initial state  ∑-  input alphabet or terminals  Δ - output alphabet  δ - transition function δ:Q×∑ → Q  λ - output function λ: Q→O  1. Moore Machine is : a) FA without input b) FA with output c) NDFA with input d) None of the above Answer: b Explanation: Finite automaton with an output is  categorized in two parts: Moore M/C and Mealy M/C. 2.Which of the following is uesd as  output alphabet  in moore machine? a) δ b) ∆ c) ∑ d) None of the above Answer-b 3.Which of the following produce output for moore machine?  a) λ:...
Read more

Question Bank of Theory of Automata & Formal Languages

  Long Answer Question Bank Theory of Automata & Formal Languages  UNIT 1 1.       Find closure of each state and give the set of all strings of length 3 or less accepted by automaton. 2.       Define DFA, NFA & Language? 3.       State and prove Myhill Nerode Theorm 4.       Design a DFA to accept string of 0’s & 1’s when interpreted as binary numbers would be multiple of 3 5.       Find closure of each state and give the set of all strings of length 3 or less accepted by automaton. 6.       Convert following NFA to DFA using subset construction method 7.       Write DFA to accept strings of 0’s, 1’s & 2’s beginning with a 0 followed by odd number of 1’s and ending with a 2. 8.       Construct D...
Read more