Basics of Theory of Computation Tutorial Study Notes with Examples

Basics of Theory of Computation Tutorial Study Notes with Examples

  1. Theory of Computation

    Basics of Theory of Computation Tutorial Study Notes with Examples

    Basics of Theory of Computation Tutorial Study Notes with Examples

 Basics of Theory of Computation

  •           Computation is defined as any type of calculation. It is also defined as use of computer technology information processing. The theory of computation is the branch that deals with whether and how efficiently problems can be solved on a model of computation, using an algorithm.

Basic Definitions

Symbol          A symbol is an abstract entity i.e., letters and digits

String            A String is a finite sequence of symbols.

Alphabet      An alphabet is a finite set of symbols, usually denoted by Σ.

Language    A formal language is a set of strings of symbols from some alphabet.

Key Points

  • Generally a, b, c, ……used to denote symbols. Alphabets will represent the observable events of an automata.
  • Generally w, x, y, z used to denote words. A word will represent the behavior of an automation.

Kleene Closure

It Σ is the set of alphabets, then there is a language is which any string of letters from Σ is a word, even the null string. We call this Language closure of the alphabet. It is denoted by * (asterisk) after the name of the alphabet is Σ*. This notation is also known as the Kleene Star.

e.g.,                            if Σ = {a}, then

                                    Σ* = {Λ, a, aa, aaa, …}

 Where, Λ represents null String.

if                                  if Σ = {a, b}, then

                                    Σ* = {Λ, a, b, aa, ab, aaa, …}

Key Points

  • By using Kleene Star operation, we can make an infinite language of strings of letters of of alphabet.
  • The words in increasing order of length called lexicographic order.

 Positive Closure

The ‘+’ (Plus Operation) is sometimes called positive closure. A+ (Plus) closure never contain null value.

If                     Σ = {a}, then Σ* = {a, aa, aaa, …}

  Note :If S is the set of strings, then S* is the language S* without the word Λ.

Operations Over Words In Σ*

  • Concatenation if x, y ϵ Σ*, then x concatenated with y is the word formed by the symbols of x followed by the symbols of y. This is denoted by xy.
  • Substring A string v is a substring of a string ω if and only if there are strings x and y such that ω = xvy.
  • Suffix if ω = xv for some string x, then v is suffix of ω.
  • Prefix if ω = vy for some string y, then v is suffix of ω.
  • Reversal Give a string ω, its reversal denoted by ωR is the string speeled backwards.

e.g.,    (abcd)R = dcba

Alphabet Ʃ*

Ʃ* It is the set of all words for a given alphabet Ʃ. This can be described inductively in at least two different ways

  • Basic case The empty word ^ is the Ʃ* (notation : ^ ϵ Ʃ* )

Inductive Step If a ϵ Ʃ and x ϵ Ʃ* ,then ax ϵ Ʃ*

                                    And also xa ϵ Ʃ*  

  • Null set The language that has no words and can be represented by ɸ.

Basics of Theory of Computation Tutorial Study Notes with Examples

Follow Us on Social Platforms to get Updated : twiter,  facebookGoogle Plus

Learn JavaScript in Hindi:  Click here 

Tagged with: , ,
39 comments on “Basics of Theory of Computation Tutorial Study Notes with Examples
  1. Young Sarvey says:

    I conceive this web site has got some real good information for everyone

  2. I like the helpful info you provide in your articles. I will bookmark your weblog and check again here regularly.

  3. I conceive this web site has got some real good information for everyone

  4. Brice Ripa says:

    Don’t wear seat belts lest you drown in you own urine?

  5. With thanks! Valuable information!

  6. Jeni Fohl says:

    Black on black in the Charg I’m creepin’ Rub me the right way, you might get a genie B.o.B, black Houdini

  7. Tayna Ottrix says:

    Don’t wear seat belts lest you drown in your own urine?

  8. I conceive this web site has got some real good information for everyone

  9. Don’t wear seat belts lest you drown in your own urine?

  10. Bryon Turvey says:

    Don’t wear seat belts lest you drown in your own urine?

  11. Black on black in the Charger I’m creepin’ Rub me the right way, you might get a genie B.o.B, black Houdini

  12. With thanks! Valuable information!

  13. Kasey Lagazo says:

    With thanks! Valuable information!

  14. Mary Worthey says:

    Don’t wear seat belts lest you drown in you own urine?

  15. Black on black in the Charger I’m creepin’ Rub me the right way, you might get a genie B.o.B, black Houdini

  16. Don’t wear seat belts lest you drown in you own urine?

  17. Black on black in the Charger I’m creepin’ Rub me the right way, you might get a genie B.o.B, black Houdini

  18. With thanks! Valuable information!

  19. Erline Huska says:

    Black on black in the Charger I’m creepin’ Rub me the right way, you might get a genie B.o.B, black Houdini

  20. here! Good luck for the next!

  21. Black on black in the Charg I’m creepin’ Rub me the right way, you might get a genie B.o.B, black Houdini

  22. Hans Kamens says:

    Black on black in the Charg I’m creepin’ Rub me the right way, you might get a genie B.o.B, black Houdini

  23. Don’t wear seat belts lest you drown in your own urine?

  24. Valeri Derr says:

    Don’t wear seat belts lest you drown in your own urine?

  25. Don’t wear seat belts lest you drown in you own urine?

  26. With thanks! Valuable information!

  27. of writing i am as well delighted to share my know-how here with colleagues. https://php665.com/

  28. Black on black in the Charg I’m creepin’ Rub me the right way, you might get a genie B.o.B, black Houdini

  29. Luetta Say says:

    With thanks! Valuable information!

  30. Don’t wear seat belts lest you drown in you own urine?

  31. Black on black in the Charg I’m creepin’ Rub me the right way, you might get a genie B.o.B, black Houdini

  32. Black on black in the Charger I’m creepin’ Rub me the right way, you might get a genie B.o.B, black Houdini

  33. I ‘m pretty sure that you’re uber reactionary in this reasoning just to argue.|

  34. You come up with some insightful points within this post, but aren’t you oversimplifying something fundamental?

  35. Are you gonna to share more concerning this subject? I figure you may be witholding some of your unpopular opinions, but I would certainly enjoy hearing them 😀

  36. Are you okay? I’m worried about you. Please be ok!

  37. You made some first rate factors there. I seemed on the internet for the difficulty and located most people will go together with with your website.

  38. I liked as much as you will obtain performed right here. The comic strip is attractive, your authored subject matter stylish. nonetheless, you command get got an shakiness over that you want be turning in the following. in poor health undoubtedly come more formerly again as exactly the same just about a lot steadily inside case you defend this increase.

  39. Sincerely-thank you-Any chance you will add to this?

Leave a Reply

Your email address will not be published. Required fields are marked *

*