#propertiesofstringintheoryofcomputation

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 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

The Sequence Of Symbols From The Alphabet Σ Is Called String. String Is Denoted By ' w ', If ' w ' Is Any String Define Over Alphabet Σ Then The Number Of Symbols Involved In The String ' w ' Is Called As Length Of String. In Theory Of Computation Length Of String Is Denoted With |w|. Example - w1= 0101    |w1| = 4 w2= 010110    |w2| = 6     Empty String - If The Length Of The String Is ZERO Then It Is Called As Empty String. Example - w = E   |w| = 0   Important Points To Remember If I ADD " w " With " ε", I Can Also Add Like This " ε" With " w", Ultimately I'll Be Getting " w " Only. See Below w+ε=ε+w=w Here " ε " Is The Identity Element Over The Addition Operation. Identity Elements Means If I'm Adding ε (epsilon) Or If I'm Doing Anything With ε (epsilon), I'll Only Get The String Which I'm Adding With ε.   If I Perform Concatenation Operation, I'll Concaten  ε With w, I'll Get ' w ' Only, See Below w ε = ε w = w I Can Say " ε " Is The Identity Element Over The Concatenation Operation. I Mean If I Want To To Concaten String(w) With Epsilon(ε), I'll Get " w " Only, String Only.  

What Is Mean By Substring?

Substring Means It Is A Part Of String We Can Say. Definition- Let u,w Be The Two String Define Over The Alphabet Σ, u Is Said To Be Substring Of w, If u Occurs In w As It Is In The Same Order. Example - w = GATE, How Many u's (substring) I Can Get From w?   1) First One We Get Is (string)w = ε (Epsilon) Is The Substring, The Length Of This Zero(0) , |w| = 0   2) Next, What Is Length " 1 " Of The String " w"? If w = GATE (4 Length String) Then If We Need Substring Of Length 1 From This String, We Will Get G A T E Each One Is Of 1 Length. So Total We Can Get 4 Substring From w String.   3) If Talk About Length 2 I'll Get GA, AT, TE These Are The Substrings I'll Get From The String w=GATE I Cannot Get GE or GT or AE Because If You See The Definition Of Substring, The Substrings Should Be In Order.   3) Lets See Length 3 w = GATE (w Is Our 4 length String) GAT, ATE Are The Possible Substrings, Of GATE   4) 4 Length GATE Is Also Substring Of The String.   I'll Tell You A Basic Formula With Which You Can Get The Possible Substrings From A Given String. If The Given String Is Distinct, Means If The Symbol In The Is Not Repeated Twice, Then The Formula For Getting Total Number Of Substrings Is n(n+1)/2+1 for |w|=n    

GATE(4 Length String Without Having Repeated Symbols) Can Create 11 Substrings.    

Substrings

There Are Two Types Of Substrings, They Are Trivial (Improper) Substring And Non-Trivial (Proper) Substring.

    There Are Two More Definitions Which Are Connected With Substring They Are Prefix, Suffix   Prefix - The Sequence Of Starting Symbols Is Called Prefix. Example:- suppose string (w)= GATE The Prefix For This String Is G, GA, GAT, GATE,ε(Epsilon)   G,GA,GAT Are Proper Prefix And GATE,ε Are Improper(Trivial) Prefix.   Suffix - The Sequence Of Ending Symbols Is Called Suffix. Example:- Suppose string (w)= GATE The Suffix For This String Is E, TE, ATE, GATE,ε   E, TE, ATE Are Proper Suffix. And GATE,ε Are Improper(Trivial) Suffix.   I'll Tell You A Generalize Formula With Which You Can Find Prefix And Suffix Of Any String If |w| = n, Then Total Number Of Prefix And Suffix =n+1   whatever The number Of symbols is there like w=GATE, I.e 4 Symbols.i.e 4+1=5 Prefix Of GATE Is G, GA, GAT, GATE, ε, Total 5 Suffix Of GATE Is E, TE, ATE, GATE,ε, Total 5    

Formulas You Have To Remember Are