#theoryofcomputation

If You Have the Ability To Think About A Problem These Problems Are Damn Eay For You, Lets Understand And Solve The Questions About Language In Theory Of Computation. Before Solving Questions I Hope You Understood About Language Which I Explained In Previous Post, If You Have Not Read, Click Here If You Know About Language Already, let's Solve The Questions On Language

  Q) Choose The Correct Statement From The Following. a) Every Regular Language Is Finite b) Every Non-Regular Language Is Finite c) Every Regular Language Is Infinite d) Every Non-Regular Language Is Infinite   Answer - d) Every Non-Regular Language Is Infinite Explanation - If You See The Language Hierarchy, Every Non-Regular Language Is Infinite

  Q) Which Of The Most Appropriate Answer For Finite Language. a) L Is Regular b) L Is CFL c) L Is CSL d) L Is REL   Answer -  L Is Regular   Explanation - Yes, L Is Regular Is The Most Appropriate Answer Because CFL, CSL, REL May Or May Not Be Appropriate.

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?

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. If You Have Puzzle Solving Ability This Subject Is Very Very Easy For You. In This Subject We Will Understand About Algorithm, Computation, Software & Hardware And The Purpose Of All These. Do You Know The Limitations Of Computer? Do You Think The Computer Can Solve Any Problem? Yes, There Are Problems Which Cannot Be Solved By Computer.  

Let's Understand The Purpose Of Theory Of Computation

I Want To Create A Mathematical Model For My Computations, Which Reflects From My Computer. What Is Computation? The Action Of Mathematical Calculation. The Task Which Can Be Performed By An Electronic Device, Like Calculator, Computer Etc. For Example - If I Want To Add 1+3, Using The Help Of Calculator I Can Solve This Or I Can Solve This Using My Computer. But, If I Want To Perform This Task Using Electronic Device, For Computation, I Have To Create Steps, I Have To Create Algorithm, So That I Can Solve This Problem.   If We Go Into The Past Years, In 1930's The Mathematicians, Logicians When They Were Trying To Understand The Meaning Of an A " Computation", A Central Question Asked Was Can Whether All Mathematical Problems Can Be Solved In Systematic Way. Then They Talked About Software And Hard Ware And Algorithms Etc. " Computation " Is The Word Which Came Out From Their Brain's. In Theory Of Computation, There Are Different Theories Came And Went Back In Their Brain.   In This Subject We Will Understand About These These Theories Under Theory Of Computation (i) Complexity Theory (ii) Computability Theory (iii) Automata Theory

Complexity Theory -

You Already Know About Complexity Theory, In Your Other Subjects. In Complexity Theory, I'll Categorize Problems Into Two Parts. If The Problem Is Easy, The Problem Will Be Called As Easy. If The Problem Is Hard, The Problem Will Be Called As Hard. But How We Can Categorize A "Problem" Is "Easy" Or " Hard", How Can We Say "This Problem Is Easy And This Problem Is Hard?" If The Problem Is Easy To Solve It Is Easy,If The Problem Is Hard To Solve It Is Called As Hard.This Will Not Happen In Computer Science. Easy For Example - If I Want To Search A Phone Number From A Phone Number Directory Which Has 'n' Number Of Phone Numbers.I'll Put A Searching Algorithm And I'll Get That Phone Number I Need.I'll Tell You The That Searching Algorithm Complexity And You Already Have Idea About Searching Algorithm's. One More Example - Imagine That I Have 1Lakh Numbers And I Want To Arrange That Numbers In To Ascending And Descending Order. And I'll Put A Sorting Algorithm And I'll It Into Ascending And Descending Order. Hard Example - If I Want To Create Time Table Lecturers And Subjects For Different Time, It Is Little Hard, The Problem Will Be Solved For Sure But I Cant Know The Exact Time,Those Type Problems Comes Under Hard Category.   In Complexity Theory I Have To Divide Problems In To Easy And Hard.  

 Computability Theory -

In Computability Theory I Should Divide Problem Into Two Categories.1) Solvable 2) Unsolvable The Problem Which I Can Solve By Showing A Mathematical Proof Comes Under 'Solvable' , The Problem Which I Cant Solve Using A Algorithm Or Any Of My Mathematical Methods Comes Under Unsolvable, Until Someone Solves It. For Example - Imagine I Have Problem Which I Cant Solve Using The Algorithms And Methods I Have Today In My Machine, The Problem May Be Solved After 50 Years But Today For Me It Is Unsolvable And The Problem Comes Under The List Called ' Unsolvable '  

Automata Theory

Today I came across a very interesting post on I/O Complexity, an additional way of characterizing the complexity of a computation. The following abstract, to tease you out, is from Robert Harper's Existential Type blog (his full article is here). Relevant is the slideshow on Cache- and IO-Efficient Functional Algorithms.