#AutomataQuestionsandanswers

[smartcherryposts]

Theory Of Computation Practice Questions

We Can Understand The Relation Between The Machines And The Expressive Power Of Each Automata By Seeing Above Picture. But With What Basis The Above Relation Is Made. Why Finite Automata Is Less Than Pushdown Automata And Why Pushdown Automata Is Less Than Linear Bounded Automata And Why Linear Bounded Automata Is Less Than Turing Machine. Let's Understand. Why Pushdown Automata Accepts More Languages Than Finate Automata? Why Turing Machine Accepts Accepts More Languages Than Pushdown Automata?      

FINITE AUTOMATA

FA -> FA + 0 Stack

In Finite Automata There Is A Stack Memory, Where I Don't Use Extra Memory Other Than Stack Memory. Like Whatever Memory Needed For States And Transitions, I'll Have In Finite Automata. If I Want Perform Extra Task, I'll Not Have Extra Memory, That Is Why FA -> FA + 0 STACK Finite Automata = Finite Automata + 0 Stack ( 0 Stack Means Without Anyother Memory) Finite Automata Is Independent, Which Have Stack Memory.  

PUSHDOWN AUTOMATA

PDA -> FA + 1

Pushdown Auotmata Accepts More Languages Than Finite Automata. In Pushdown Automata - Finite Automata + 1 Stack Memory Will Be There. PDA -> FA + 1 Stack    // Here 1 Stack Memory Will Be Added In PDA, The Languages Which Are Not Accepted By Finite Automata, Those Languages Maybe Accepted By PUSHDOWN AUTOMATA  

Turing Machine

Turing Machine - FA + 2 STACK There Are Languages Which Are Not Accepted By Pushdown Automata, Those Languages Are Accepted By Turing Machine. TM= FA + 2 STACK //  In Turing Machine, 2 Stack Memories Attached, For Accepting More Languages, If I Add Finite Auotmata With 2 Stack Memories, It Becomes Turing Machine.   I'm Not Telling You About Linear Bounded Automata(LBA) Because Still Research Is Going On On LBA.That Is Why The Reason I'm Not Telling You About LBA Here.   Basically, You Have To Understand Why TM Is So Much Powerful, It Has FA With 2 Stacks Memory.It Has More Memory.   Do You Have Doubt What Is ->  FA + 3 Stacks ? This Is A Turing Machine.   There Is No Difference Between FA+2 STACKS & FA + 3 STACKS   FA+2 STACKS And FA + 3 STACKS Both Are Same Powerful. If I Say FA + n Stacks ( n≥2 )   All Are Same Powerful. FA+2 STACK & FA + 3 STACK & FA + n STACK , All Are Equally Powerful. Example E(FA+2 STACK)=E(FA+n STACK) //Expressive power of FA + 2 STACK Is Equal To Expressive Power Of FA + n STACK   This Is Basically Called As RAM,If You Increase The Memory Of The RAM, It Can Accept Same Number Of Languages. In Simple Words ' The Same Number Of Languages For Will Be Accepted Even If You Increase Or Decrease The RAM Size.

AUTOMATA

I Have Divided Automata Into Three Parts,1) LA 2) LG 3) COMPUTATIONAL MODEL   Language Acceptor LA Means Language Acceptor, If I Give Language As Input To Any Machine, Machine Gives Me Output Like ' YES ' Or ' NO ' Means Language 'Accepted' Or 'Rejected'   I Have Three Machine FA, PDA, TM. In these Models, Some Will Be LA ( Language Acceptor ), They Accept Or Reject Languages.   Language Generator I Have Three Machine FA, PDA, TM. In These Models, Some Will Accept-Languages And Generate Different Languages. Those Type Of Auotmata Are Called As Language Generator Automata, This Model Is Called Language Generator.   Computational Model If I'm Giving Input String To The Machine And If I'm Getting Result From That Machine, If I'm Getting A Computational Value Back As Result. For Example If Im Giving   2+3  // As Input The Calculator Gives Me Result 5. // Means I'm Getting A Value In Return As Output As Result. This Model Is Called As Computational Model.   On These Three Model, LA, LG, Computational Model, I Have Divided My Automata.

  Finite AUTOMATA FA Is Language Acceptor And Computational Model. I Dont Use FA As A Language Generator Because It Will Not Generate Any Language. Pushdown AUTOMATA PDA Is Only Language Acceptor. If I give String As Input,If My String Is Satisfying The Language Of Automata, Then My PDA Will Goto Final State Or Else It Will Goto Non-Final State. PDA Will Not Give Any Result,It Will Not Give Result By Doing Any Computation. PDA Is A Only Language Acceptor. TURING MACHINE Turing Machine Accepts All My Models.LA, LG, CM All The Three Models. Turing Machine Can Do Every Task Which Computer Performs.

    Practice Questions

5) Which Of The Following Is Wrong?

a) FA + 1 STACK  Is More Powerful Than FA B) FA + 2 STACK Is More Powerful Than FA + 1 STACK c) FA + 3 STACK Is More Powerful Than FA + 2 STACK d) NOTA   Answer - c)   Explanation -

  6) Which Of The Following Model Doesn't Work As Transducer?

a) FA b) PDA c) TM d) NOTA   Answer - b)   Explanation -�� The Meaning Of Transducer Is Translating, Taking Input In A Form And Giving Output In Another Form.

PDA Is Only An Acceptor Not A Result Giver, So PDA Is Not A Transducer, Which Will Not Give Output.   Share This Post With Your Friends If You Love The Explanation.             Read the full article