theory of computation notes. introduction and mcq points

TOC notes

1. Theory of Computation
SANGEETH N.

2. Syllabus
TheoryofComputation:Regularlanguagesandfiniteautomata,
context-freelanguages&pushdown automata,recursively
enumerablesets&Turingmachines,undecidability

3. Topics
●BasicTerminologies
●RegularExpression

4. Basic Terminologies
●Symbol:Asymbolisthesmallestbuildingblock,whichcanbeany
alphabet,letter,orpicture.
●Alphabets:Theyareasetofsymbols,whicharealwaysfinite.
Example:Alphabetsofbinarydigits,decimaldigits.

5. Basic Terminologies
●String:Astringisafinitesequenceofsymbolsfromsomealphabet.
●Astringisgenerallydenotedaswandthelengthofastringisdenoted
as|w|.
●Listoutstringshavinglengthinthealphabetsetcontaining{a,b}.

6. Basic Terminologies
●Foralphabet{a,b}withlengthn,numberofstringscanbegenerated=2
n
●Generalcase:IfthenumberofsymbolsinthealphabetΣisrepresentedby|Σ|,
thenanumberofstringsoflengthn,possibleoverΣis|Σ|
n

7. Basic Terminologies
●ClosureRepresentation
○L
+
: It is a Positive Closurethat represents a set of all strings
except Null or ε-strings.

8. Basic Terminologies
●ClosureRepresentation
○L
*
: It is “Kleene Closure”, that represents the occurrence of certain
alphabets for given language alphabets from zero to the infinite
number of times.

9. Basic Terminologies
●Listoutthestringacceptedbya*

10. Basic Terminologies
●Listoutthestringacceptedbya
+

11. Basic Terminologies
●Listoutthestringacceptedby{a,b}*

12. Basic Terminologies
●Alanguageisasetofstrings,chosenfromsomeΣ*
●AlanguageisasubsetofΣ*‘.
●Alanguagethatcanbeformedover‘Σ‘canbeFiniteor
Infinite.

13. Basic Terminologies
●Finite–Listoutstringoflength2inthealphabet{a,b}*
●Infinite–Listoutstringstartingwithainthealphabet{a,b}*

14. Regular Expression
●Regular Expressions are patterns that are used to denote
languages.
●An expression is regular if:
○ɸis a regular expression for regular language ɸ.
○ɛis a regular expression for regular language {ɛ}.
○If a∈Σ, a is regular expression with language {a}.

15. Regular Expression
●An expression is regular if:
○If a and b are regular expression, a + b is also a regular
expression with language {a,b}.
○If a and b are regular expression, ab (concatenation of a
and b) is also regular.
○If a is regular expression, a* (0 or more times a) is also
regular.

16. Regular Expression
●Write the regular expression for strings starting with a in the
alphabet set {a,b}

17. Regular Expression
●Write the regular expression for strings end with b in the
alphabet set {a,b}

18. Regular Expression
●Write the regular expression for strings start with a and end
with b in the alphabet set {a,b}

19. Regular Expression
●Write the regular expression for strings start with a or end
with b in the alphabet set {a,b}

20. Regular Expression
●Write the regular expression for strings contain a substring
abbin the alphabet set {a,b}

21. Regular Expression
●Find the language obtained from regular express 1*01*.

22. Question -1
Which one of the following languages over the alphabet {0,1} is
described by the regular expression?
(0+1)*0(0+1)*0(0+1)*
(A) The set of all strings containing the substring 00.
(B) The set of all strings containing at most two 0’s.
(C) The set of all strings containing at least two 0’s.
(D) The set of all strings that begin and end with either 0 or 1.

23. Question -1
Which one of the following languages over the alphabet {0,1} is
described by the regular expression?
(0+1)*0(0+1)*0(0+1)*
(A) The set of all strings containing the substring 00.

24. Question -1
Which one of the following languages over the alphabet {0,1} is
described by the regular expression?
(0+1)*0(0+1)*0(0+1)*
(B) The set of all strings containing at most two 0’s.

25. Question -1
Which one of the following languages over the alphabet {0,1} is
described by the regular expression?
(0+1)*0(0+1)*0(0+1)*
(D) The set of all strings that begin and end with either 0 or 1.

26. Question -1
Which one of the following languages over the alphabet {0,1} is
described by the regular expression?
(0+1)*0(0+1)*0(0+1)*
(C) The set of all strings containing at least two 0’s.

27. Question -1
Which one of the following languages over the alphabet {0,1} is
described by the regular expression?
(0+1)*0(0+1)*0(0+1)*
(A) The set of all strings containing the substring 00.
(B) The set of all strings containing at most two 0’s.
(C) The set of all strings containing at least two 0’s.
(D) The set of all strings that begin and end with either 0 or 1.

28. THANK YOU