#TheoryOfComputationforgate

[smartcherryposts]

NFA To DFA Conversion In Theory Of Computation

NFA To DFA Conversion In Theory Of Computation Construct The DFA For The Following NFA

    DFA Using DFA Transition Table If All States Are Final The Minimal DFA Will Be

My Initial State Will Be My Final State And This Is The DFA.   Example-2

Conversion Of NFA To DFA

Find The Minimal No Of States In NFA

Solution:- Transition Table For Given Diagram

This Is One Of The Different Questions. To Solve This Question We Are Going To Use Short Cut. If You Are Expert In Constructing DFA, You Can Solve This Question Using Short Cut.   The Question Given Is "Find The Minimal No.Of States In NFA" Means We Have To Find The Minimum No Of States In Given NFA.   There Will Be No Uniqueness In NFA. If It Is Not Unique, How Can We Find Minimal States?  

Remember

If The Question Is Asked To Find Minimal No Of States, The Diagram Should Be Unique And Should Be Minimal(Optimized) We Know DFA Means Minimized, We Can Construct Unique DFA, We Can Construct A Unique DFA For A Language. It Means The No Of States In DFA wILL Be Unique.   "Every DFA Is Not NFA" We Know But Every NFA Is Not DFA   Simple We Have To Draw DFA For Given NFA We Already Drawn Many DFA From NFA's In Previous Topics.   We All Know That Procedure.   But Here To Solve This Problem Using Short Cut. If We Can Predict The Language For Given NFA, Then We Can Find DFA Easily   I Have Solved Many Problems Before In Previous Posts We Have Seen How To Construct DFA Directly In Previous Solved Problems.   I Want You To Identify The Language For The Given Nfa & For That NFA For That Language, You Have To Draw DFA. Very SImple.

If You Observe Above NFA 0,1 Is Going To q0 Then After 3 Zero's 000, It Is Going To Final State. Means String Should ContainThree Zero's(000) Continuously For Sure And Final State q3 Has Loop Of '0', It Means The String Should End With Three Zero's(000) String Compulsorily Should Contain 3 Zero's This Is The Language For This Given NFA.   DFA

  Explanation For DFA

If I Get '1' , I'll Be On q0 Only If I Get '0 On 'q0' I'll Go To 'q1' If I Get '0' On 'q1' I'll Go To 'q2' If I Get '0' On 'q2' I'll Go To 'q3'(FINAL STATE) Because I Should Reach Final State Once I Get 3 Zero's String If I '1' On 'q1','q2','q3' I'll Go To Initial State 'q0' And I'll Start Machine Again I Cant Go To Dead State If I Get '1' On q1,q2,q3 If I Go To Dead State I Can't Get Back And I Cant Start The Machine Again   Read the full article

[smartcherryposts]

Theory Of Computation - Practice Questions On Language

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.

Read the full article

[smartcherryposts]

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 Read the full article

[smartcherryposts]

Types Of Languages - Types Of Grammars - Types Of Automata(Machine)

Types Of Languages - Every Language Have Two Components, One Is Grammer And Another One Is Acceptor Or Machine. Grammer Generates Language, Acceptor Accepts The Language, Acceptor Is A Machine.

If The Language Changes Then Its Grammer Is Also Changes, If The Language Changes The Machine Also Changes, Which Accepts The Language. We'll Understand The Types Of Languages.

Types Of Formal Languages

According To The Memory, According To The Grammer And Change In Grammer, Are The Reasons For To Have Different Language Necessarily. Let Know Why To Have Different Languages. To Accept A Language Few Machines Needs Memory, Few Machine Don't Need Memory In It To Accept-Language. According To The Machine Architecture Or According To The Machine Model, I Have Divided Languages Into Different Types. Based On The Grammer I Have Divided Languages Into Different Types.   First Language In Types Of Formal Languages Is Regular Language, In ShortCut, I'm Writing Regular Language As RL RL Means Regular Language Remember This, In Theory Of Computation We Mostly Use Shorts Cuts. I Use Regular Language, I Don't Need Memory Size In The Machine For This Language.   Second Is Context Free Language (CFL) Context Free Grammer Is Little Different Compare To Regular Language, I Need To Use Stack Memory For Context Free Grammer. Third Is Context-Sensitive Language (CSL) I Need To Use More Than One Memory In Context-Sensitive Language, Fourth Is Recursive Enumerable Language (REL)   According To The Machine Architecture, According To The Grammer I Have Divided Languages Into Four Types. According To The Memory Size And Memory Model These Are Types Of Languages, These Are The Types Of Languages We Have.  

Types Of Grammars

The Set Of All The Rules Which Are Used For Generate A String Is Known As Grammer. I Have Follow Few Conditions To Generate A String, Those Conditions Are Created By Grammer. Example - Few Rules I'm Writing Here S->AB // S Gives AB, S Means Starting Symbol,If I Want To Create A String, I Have Start, So This Is The Symbol For Starting A String. And Which Is Denoted With Capital Letters, We Call These Capital Characters As Non- Terminals Or Variables, In C Language You Will See Variables, Similarly Here These Variable Values Can Be Changed.   A->a // A Gives Small a, The Small Characters, Can Be Seen On Left Side, Those Are Called Terminals, Terminals Means We Cant Expand These And We Cant Change, If I Get ' a ' In A String, I Can't Change That 'a ', Whereas If I Get " AB " In Any String, I Can Replace It With      ' a ', That's Why We Call S->AB As Variables And ' a ' As Terminals.   B->b // B Gives Small b   For Example - If I Want To Create A String, I Have Input Alphabets Σ= {a,b}, I Have To Create String Using 'ab', By Using The Above Grammer Rules Can I Create A String ?? Lets See

Using The Given Set Of Rules Of Grammer We Created A String ' ab ' ' S ' Is My Starting Symbol, Always I Need To Start With Starting Symbol ' S ' Then I Need To Replace ' S ' With The Variable I Have On The Left Side Of ' S ' i.e ' AB ' , In The Place Of ' AB ' It Is Possible To Have Variables And Non- Variables And Terminals. I Replaced ' S ' With The Variables ' AB '   I Have A Set A Rule i.e A - > a, In Which A Replaces ' a ' , i Replaced ' A ' With ' a ' Similarly B- > a , I Replaced b In The Place Of B   If You Traverse The String, The Charecters Came In The Leaf Node, That Combination We Call As " String " So ab Is The String I Have Generated.   'ab' Is The String Generated Using The Set Of Rules Of Grammer Given And By Taking The Input Alphabets Σ={a,b} And That String Gets Satisfied For That Language Of That Grammer. Like That Grammer Rules Are Written In This Way.   Types Of Grammer Regular Grammer (RL) Context Free Grammer (CFG) Context Sensitive Grammer (CSG) Recursive Enumerable Grammer (REG) Or Unstructured Grammer.   According To The Language, I'll Have Its Own Grammer, Every Language Has Its Own Grammer.If I Create A String Using A Particular Grammer, That Required String Represent Its Language.  

Types Of Automate (Machine)

The Language I'm Talking, To Accept That Language,It Need's A Machine It Needs A Mathermatical Model. Why I Need Machine? Lets Understand With An Example.   Imagine That I Have Took A Language Called L. L= Set Of All The Strings Starts With ' a ' // Means All The Strings In The Language Starting Symbol Should Be ' a ' Input Alphabets Σ = {a,b} ={a,ab,aab,aba,abb,aaab,abbab,.....} // Generated Strings I Can Create Infinite Strings In This Language. I Can Create Any Number Of Strings Using Starting ' a ' Symbol. I'll Store All These Strings In Machine.   Imagine That I Need To Search For A String Which Satisfies This Language. If I Give A Input String 'aba'  To Machine And I'll Ask Machine To See The String Is There Or Not In The Language ' L '   Machine Searches ' aba ' String In All The Stored Stored Strings Where It Is There Or Not.   I Want To Talk Practically, There Are Infinite Strings Which Accepts The Language ' L ' In The Machine, Storing Large Number Of Strings In My Machine Is Little Difficult Because Every Machine Has A Problem Called Memory.I'll Have Limioted Amount Of Storage Capacity, I Cant Store Infinite Number Of Data.   So, If I Get Any String As Input, I Need A Mechanism With Which I Can Judge That Wheather This String Satisfies My Language Or Not. So,I Need To Create A Machine Which Gives Output As " Yes " Or " No".   Thats Where, What Will Be The Input For My Machine? My Machine Input Will Be 'Language' And Input String. And What Should I Create? I Should Create A Finite Machine. Finite Machine Means, Where Finite Number Of Decisions Taking Ability Will Be There And Finite Number Of States Will Be Available. Which Gives Me "Output" Saying That "This String Is In This Language" Or Not   If I Can " I Can Also Store All The Infinite Strings Of The Language In My Machine" And Whenever I Get A Input I Can Do Searching Operation To Find The Input String From The Stored Strings. But My Language Is Infinite,That's Why I Cant Store Infinite Data In Finite Memory. So, I Need A Type Of Representation, Which We Call It As Finite Machine.   We Call That Finite Machine As Finite Automata In This Theory Of Computations(Automata), We Need To Create Lot Of Automata( Machine)

If You Observe The Picture, The FA(Finite Automata) Takes Input As Language And Gives Out Put As ' Yes ' or ' No ' For This Language If The Input String Given To The Automata Is Valid Or Acceptable To It, Then My Finite Automata Gives Output As ' Yes ' If The The Input String That Doesn't Satisfy The Language, That Doesn't Satisfy The Restrictions Of The Language,For That Finite Automata Gives Output As ' No ' So According To The Language, I Have To Change The Machine,If My Language Is Finite Language, My Machine Is Finite Automate Because Finite Automata Accepts Finite Language. If The Language And Its Grammer Changes, If I Require Memory, I Need To Attach Memory To Finite Automata(Machine) To Accept Those Languages. According To That, My Machine Is Divided Into Different Types.   Types Of Automata Finite Automata (FA) PushDown Automata (PDA) Linear Bounded Automata (LBA) Turing Machine According To The Memory Requirement, Memory Attachment, We Divided It Into Different Types. 1.Finite Automata In Finite Automata, There Will Be Finite Number Of States. We won't Attach Any Memory To This. 2.Push Down Automata Here I Also Required Stack Memory, Because Few Languages Will Get Accepted By Push Down Automata, So One Stack Memory Gets Attached To It. 3.Linear Bounded Automata Here Also I Need I Required One More Stack Memory Because The Languages Accepted By Linear Bounded Automata, There I Will Be Required More Memory. 4.Turing Machine Turing Machine Is Big Machine Among All. Turing Machine Is Also Called Abstract Model Of Computer Because Whatever The Problem's Can Be Solved By Turing Machine, All Those Problems Can Be Solved By Computer.   So This Is The Information About Automata(Machine), Grammars And Languages.   If You Like The Explanation, Install Smart CSE Android App From Google Play Store, So That You Can View All The Topics Of Theory Of Computation In Your Mobile.

  Thanks                               Read the full article

[smartcherryposts]

Power Of Alphabets In Automata

Power Of Alphabets (∑) In Automata, If ∈ Is An Alphabet Then ∑k Is The Set Of All The String From The Alphabet ∈ Of Length Exactly k. Example - ∑= {a,b}  // a & b are input alphabets We Are Talking About ∑k  (Sigma To The Power Of k)   ∑ 1= Set Of All The String Of Length 1. ={a,b} // Formed String   ∑ 2= Set Of All The String Of Length 2. ={aa,ab,ba,bb} // Formed Strings   ∑ 3= Set Of All The String Of Length 3. ={aa,ab,ba,bb,aab,aba,baa,bba} // Formed Strings   ∑ 0= Set Of All The String Of Length 0 (Empty Set) ={∈} // Empty Set Or Epsilon     Positive Closure Of  ∑ ∑+=∑1 ∪ ∑2∪ ∑3 ∪ ∑4...... Kleen Closure Of  ∑ ∑*= ∑0 ∪Σ1 ∪ ∑2∪ ∑3 ∪ ∑4...... // Kleen Closure Of  ∑ Is A ∪niversal Language  

To Remember The Above, Remember The Following Rules

(a)  ∑+ ⊂ ∑*   // Sigma To The Power Of Plus Is The Subset Of SigmaTo The Power Of Star (b) ∑* = ∑+ ∪ {∈} // Sigma To The Power Of Star Is Equal To Sigma To The Power Of Plus ∪nion Epsilon ( Empty Set) (c) ∑+ = ∑*- {∈} (d) ∑* ∪ ∑+ = ∑* (e) ∑* ∩ ∑+ = ∑+ (f) ∑* ∑+ = ∑+ (g) ∑* ∑* = ∑* (h) ∑+ ∑+ = ∑+ - ∑1             Read the full article

[smartcherryposts]

Theory Of Computation Introduction

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?

A Language Is A Combination Of Strings On Given Certain Conditions.   Example - ∈ = {a,b} // Input Alphabet Using The Above Alphabet, You Have To Create String With The Length Of 2. L1=Set Of All The Strings Of Length 2 = {aa,ab,bb,ba} This Set Is Called As Finite Set, Any Set In Which We Can Count Elements Is Called Finite Set Because We Have Finite Number Of Elements In The Set. Using The Language We Created This Finite Set, Where The Set Contains Countable Elements, This Language Is Called As Finite Language.   Example 2 ∈ = {a,b} L2= Set Of All Strings Starts With ' a ' = { a,aab,aab,aba,abba,abab,.......} This Set Is Called As InFinite Set, Any Set In Which We Can Not Count Elements Is Called InFinite Set Because We Have InFinite Number Of Elements In The Set. Using The Language We Created This InFinite Set, Where The Set Contains UnCountable Elements, This Language Is Called As InFinite Language.   In This Post, We Have Understood About Symbol, Alphabet, String, Language.I Hope You Understood If You Have Any Doubts Comment Below.           Read the full article

[smartcherryposts]

Theory Of Computation

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

In Automata Theory I Should I Learn About Different Mathematical Models.Finite Automata,Context Free Grammer, Turning Machine Are Few Methods And There Are Lot More Methods In Automata Theory. These Three Are Mathematical Model Which Represents Computations.   Fnite Autometa,Context Free Grammer,Turing Machine Here I Have To Know Which Method Is Powerful Which Can Solve More Problems. If I Talk About Finite Automata, Finite Automata Has Some Restrictions,Where I Cannot Solve Multiple Problems.Some Problems Can Be Solved And Some Finite Autometa Cannot Solve. Turing Machine Can Solve Problem Which Can Be Solved By The Finite Automata And It Can Solve The Problem Which Cannot Be Solved By Finite Automata.   And Here I Have To Know "How A Problem Can Be Categorized" And I Should Know "Which Model Solves That Problem. We Will Understand Indetail About These Models And Categorization.   Basically Theory Of Computation My Main Focus Will Be On Automata Theory, Then We Will Discuss About The Computational Theory.       To Understand This Subject You Need To Have Logical Thinking,One Problem Will Not Depend On Other Problem, Each And Every Problem Is Unique In This Subject.                         Read the full article