Monday, May 27, 2019
Home > Theory Of Computation > Part 1: Theory Of Computation Practice Questions

Part 1: Theory Of Computation Practice Questions

Theory Of Computation Practice Questions Solved And Explained Briefly.

 

Which Of The Following Statement Is Correct?

a) DFA Is More Efficient Than NFA

b) NFA Is More Efficient Tham Than DFA

c) DFA Is More Powerful Than NFA

d) NFA Is More Powerful Than DFA

 

Answer Is a)

Explanation 

E(NFA)=E(DFA)

Expressive Power Of NFA Is Equal To DFA, The Languages Accepted By NFA Are Equal To The Languages Accepted By DFA.

I Can Draw NFA For All RL.

I Can Draw DFA For All RL.

 

Hence DFA Is More Efficient Because I’ll Have Only One Router Or Way.

 

2) Choose The Incorrect Statement From The Following.

a) DPDA Is More Efficient Than NPDA

b) Capabilities Of DPDA & NPDA Are Same

c) NPDA Is More Powerful Than DPDA.

d) NOTA

 

Answer – b

Explanation

E(NPDA)≥E(DPDA)

 

3) For Which Of The Language An Automata Can Be Constructed In Both Deterministic And Non-Deterministic Mode To Accept That Language.

a) Regular

b) CFL

c) REL

d) NOTA

 

Answer – a) & c)

 

Explanation

a)E(NFA)=E(DFA)

b) E(NPDA) ≥ E(DPDA)

c) E(NTM)=E(DTM)

d) ×

 

4) Choose Correct Statement From The Following

a) DFA Is More Powerful Than DPDA

b) DPDA Is More Powerful Than DFA

c) NFA Is More Powerful Than NPDA

D) NOTA

 

Answer – b)

 

Explanation

a) FA <PDA, So DFA, Is Not Powerful Than DPDA

b) FA <PDA, So DPDA Is Powerful Than DFA

c) FA <PDA, So NFA Is Not Powerful Than NPDA.

d) ×

 

 

3 thoughts on “Part 1: Theory Of Computation Practice Questions

Leave a Reply