#theoryofcomputationbook

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

Theory Of Computation Is Also Known As Core Subject Of Computer Science. If You Are A Logical Thinker, If You Love To Learn Mathematics, This Subject Is Very Easy For You.   Let's Understand The Importance Of Theory Of Computation(TOC) In Computer Science And Basic Terminologies Used In Theory Of Computation.  

First We Have To Know What Is Mean By Symbol ?

You'll Be Seeing Lot Of Symbols In Your Day-to-Day Life, If You Observe The Keyboard You'll Be Seeing A-Z Alphabets And 0-9 Numbers. And You'll Be Seeing Special Characters, All These Are Considered As Symbols. Every Symbol On The Keyboard Has Specific Meaning. Symbols - A,B,C 0,1,2 @,#,$(,)

  What Is Alphabet?

We Represent Alphabets With " ∈ ", You May Have Seen This Symbol In Mathematics While Doing SUM. Here We Will Represent Alphabets With " ∈ " The Meaning Of " ∈ " Is A Particular Domain's Symbol. Alphabet As The Set Of Symbols Example - {a, b}, Which Are Always Finite  

What Is String?

String Is A Combination Of Alphabet, Any Number Of Times Is Called As String. Example - ∈ ={a,b}   // Converting Alphabet To String Set Of = {aa,ba,bb,aba,bba....}  // This Is String  

What Is Language?