Finite Automata Interview Questions and Answers | Automata Theory Solved MCQ | MCQ

1. According to Noam Chomsky Turing Machine will Accepts ___________.

a) Regular Language

b) CFL

c) CSL

d) Recursively Enumerable Language

View Answer: D

2. X  à αY | α is the production rule for_____________________

a) Regular grammar

b) Context Free Grammar

c) Right Linear Grammar

d) Left Linear Grammar

View Answer: C

3. Context Free grammar is ______________ tuple grammar

a) 3

b) 4

c) 2

d) can’t be represented.

View Answer: B

4. Type-2 grammar has production rule of the form

a) X  à αY | α  where α ε T & X,Y ε V

b) X  à Yα | α  where α ε T & X,Y ε V

c) X  à α   where α ε (V UT )* & X ε V

d) None

View Answer: C

5. Generation of language  using specific rule is called_________________

a) Derivation

b) Optimization

c) Analysis

d) None of the mentioned

View Answer: A

6. A grammar is said to be ambiguous if there exists _______________________

a) More than one LMD

b) More than one RMD

c) More than one Parse Tree

d) All

View Answer: D

7. In production rule, if one Non-Terminal symbol derives another Non-Terminal then it is known as

a) ε-Production

b) Null Production

c) Unit Production

d) Useless Symbol

View Answer: C

8.A symbol X is said to be useful if ?

a) Reachability of X from start symbol

b) X should derive terminal strings

c) Both a & b

d) None

View Answer: C

9.The machine which accepts CFL is

a) FA

b) LBA

c) PDA

d) TM

View Answer: C

10.PDA is ____________ tuple machine

a) 6

b) 4

c) 5

d) 7

View Answer: D

11.Basically FA with stack memory can be viewed as ________________.

a) TM

b) PDA

c) LBA

d) None

View Answer: B

12.Mapping function of PDA is ___________________ 

a) Q x Σ U {ε} x Γ à Q x Γ*

b) Q x Σ U {ε} à Q x Γ*

c) Q x Σ U {ε} x Γ à Q x Γ

d) None

View Answer: A

13.Which are the operations performed on stack while converting CFL to PDA?

a) PUSH and POP

b) Only PUSH

c) Only POP

d) Writing Production rule and POP

View Answer: A

14. Which are the operations performed on stack while converting CFG to PDA?

a) PUSH and POP

b) Only PUSH

c) Only POP

d) Writing Production rule and POP

View Answer: D

15. A CFG is said to be in CNF if production rule of the form

a) X  à αY | α  where α ε T & X,Y ε V

b) X  à YZ | α  where α ε T  & X,Y,Z ε V

c) Both a & b

d) None

View Answer: B

16. A CFG is said to be in GNF if production rule of the form

a) X  à αV* | α  where α ε T

b) X  à YZ | α  where α ε T  & X,Y,Z ε V

c) None

d) Both a & b

View Answer: A

17._______________________ is a general example of CPU that controls all data manipulation done by computers

 a) LBA

b) TM

c) FA

d) All

View Answer: B

18.Unrestricted grammar is also called as  

a) Type-3

b) Type-2

c) Type-1

d) Type-0

View Answer: D

19.TM is a ______________ tuple machine

a) 5

b) 6

c) 7

d) 4

View Answer: C

20. Mapping function of TM is given by  

a) Q x Γ à Q x Γ x (R/ L)

b) Q x Σ U {ε} à Q x Γ*

c) Q x Σ U {ε}x Γ à Q x Γ*

d) All

View Answer: A