Unit -I Toc.pptx

theory of coputation

1. THEORY OF COMPUTATION Unit –I FINITE AUTOMATA By, T.VISWANATH KANI,M.E., AP/CSE VCEW

2. FINITE AUTOMATA Introduction Basic Mathematical Notation and techniques Finite State systems Basic Definitions Finite Automaton DFA & NDFA Finite Automaton with €- moves.

3. Introduction The Theory of Computation is a branch of computer science and mathematics combined that "deals with how efficiently problems can be solved on a model of computation, using an algorithm ".

4. It studies the general properties of computation which in turn, helps us increase the efficiency at which computers solve problems. This is done when we estimate the validity of the solutions given by the computer through the theory of computation and then alternate the algorithms so that we can obtain a more reliable solution. This is a fast-growing branch that has helped solving problems in many fields beside computer science such as Physics, Economy, Biology and many others

5. Introduction Before introducing you to the basics of the theory of computation, I would like to talk about the Turing machine, as it plays a good role in explaining this theory: It is theoretical abstract machine used as a model of computation . It uses an infinite memory tape where the information obtained are saved, and analyze these information to determine whether the operation is feasible or not. This theory is approached through three main fields: 1- Automata theory 2- Computability theory 3- Computational complexity theory

6. 6 Alan Turing (1912-1954) Father of Modern Computer Science English mathematician Studied abstract machines called Turing machines even before computers existed Heard of the Turing test? (A pioneer of automata theory)

7. 7 Theory of Computation: A Historical Perspective 1930s Alan Turing studies Turing machines Decidability Halting problem 1940-1950s “ Finite automata ” machines studied Noam Chomsky proposes the “ Chomsky Hierarchy ” for formal languages 1969 Cook introduces “intractable” problems or “ NP-Hard ” problems 1970- Modern computer science: compilers , computational & complexity theory evolve

8. Importance of Theory of computation The theory of computation forms the basis for: Writing efficient algorithms that run in computing devices. Programming language research and their development. Efficient compiler design and construction.

9. Automata theory Automata   theory (also known as  Theory Of Computation ) is a theoretical branch of Computer Science and Mathematics, which mainly deals with the logic of computation with respect to simple machines, referred to as automata. 

10. Automata* enables the scientists to understand how machines compute the functions and solve problems. The main motivation behind developing Automata Theory was to develop methods to describe and analyze the dynamic behavior of discrete systems.  Automata is originated from the word “Automaton” which is closely related to “Automation”. 

11. Automata   theory A basic computation performed on/by an automaton is defined by the following features: A set of input symbols. The configuration states. Output. Branches of Automata theory Finite Automata (FA):  This is a computer model that is inferior in its computation ability. This model is fit for devices with limited memory. It is a simple abstract machine with five elements that define its functioning and processing of problems.

12. Computability theory The  Computability theory  defines whether a problem is “solvable” by any abstract machine. Some problems are computable while others are not. Computation is done by various computation models depending on the nature of the problem at hand, examples of these machines are: the Turing machine, Finite state machines, and many others.

13. Complexity theory This theoretical computer science branch is all about studying the cost of solving problems while focusing on resources (time & space) needed as the metric. The running time of an algorithm varies with the inputs and usually grows with the size of the inputs. They are: Upper ( Worst Case Scenario ) Lower ( Best Case Scenario ) The major classifications of complexities include: Class P Class NP

14. Why toc? • Foundation of all model computers •Deep understanding of computer and computing • Theory of pattern matching in web search • Theory of finite automata in sequential circuits • Theory of context free grammars in Compilers •Theory of computational complexity in cryptography and network security

15. Why toc? Finite automata are a useful model for many important kinds of software and hardware: 1. Software for designing and checking the behaviour of digital circuits 2. The lexical analyser of a typical compiler, that is, the compiler component that breaks the input text into logical units 3. Software for scanning large bodies of text, such as collections of Web pages, to find occurrences of words, phrases or other patterns 4. Software for verifying systems of all types that have a finite number of distinct states, such as communications protocols of protocols for secure exchange information

16. TOC Example

17. Research Areas available in ToC Design and analysis of algorithms Cryptography Quantum Computation Randomness in computation Applications of ToC Compiler design Robotics Artificial Intelligence Knowledge Engineering

18. BASIC MATHEMATICAL NOTATIONS AND TECHNIQUES Symbols- a,b,c,0,1,2,3 Alphabets-Collection of symbols representing in ∑ Strings- Array of characters ∑={0,1}-00,01,11,0000,111,... ∑={ a,b } - a,b,ab,aa,bb,abc ,... String length of ∑={1,2,3}=3 Notation of length of w: |w| Example: |011| = 3 and | ε | = 0

19. BASIC MATHEMATICAL NOTATIONS AND TECHNIQUES Empty string is denoted by ε Concatenation of strings X=0,1. Y=2 XY=012 Reversing a string Writing the symbols in reverse order U=1010001 U^R=1000101

20. BASIC MATHEMATICAL NOTATIONS AND TECHNIQUES Power of an alphabet: Let ∑ be an alphabet Then ∑^*- Denotes all the strings o ver an alphabet ∑ ∑^m – Set of all strings of length m over an alphabet ∑ For example: ∑={0,1} ∑^0= ε

21. BASIC MATHEMATICAL NOTATIONS AND TECHNIQUES ∑^1 ={0,1} ∑^2= {00,10,10,11} ∑^3= {001,100,101,110,111,011,...} ∑^* =?

22. Kleene closure

23. Positive Closure

24. Language Definition  − A language is a subset of ∑* for some alphabet ∑. It can be finite or infinite. Example  − If the language takes all possible strings of length 2 over ∑ = {a, b}, then L = { ab, aa, ba, bb }

25. Operations on Languages Concatenation Reversal Kleen closure Positive closure Union Intersection

26. Concatenation , Kleene closure If L1 and L2 are two languages, we define:the concatenation of L1 and L2, denoted by L1L2, as the set of all words given by the concatenation of any word in L1 with any word in L2. L={ x|x = uv and u belongs to L1 and v belongs to L2} Ex:If L = {001, 10, 111 } and M = {ǫ, 001 } then L.M = {001, 10, 111, 001001, 10001, 111001 } The Kleene closure of L, denoted by L*, as the language: L*=L0 U L1 U L2 U ... where L0 is the empty string and Ln=Ln-1L is the language consisting of the words of length n for n>0.

27. Union , Intersection The union of two languages L and M, denoted L ∪ M, is the set of strings that are in either L, or M, or both. Example If L = {001, 10, 111 } and M = {ǫ, 001 } then L ∪ M = {ǫ, 001, 10, 111 } Intersection: Let L and M be the languages of regular expressions R and S, respectively then it a regular expression whose language is L intersection M.

28. Set A set is an unordered collection of objects or an unordered collection of elements. Sets are always written with curly braces {}, and the elements in the set are written within the curly braces. Examples The set {a, b, c} has elements a, b, and c. The sets {a, b, c} and {b, c, b, a, a} are the same since order does not matter in a set and since redundancy also does not count.

29. Types of Set 1 .Finite Set A set consisting of a natural number of objects, i.e. in which number element is finite is said to be a finite set. Consider the sets A = { 5, 7, 9, 11} and B = { 4 , 8 , 16, 32, 64, 128} Obviously,  A ,  B  contain a finite number of elements, i.e. 4 objects in  A  and 6 in  B . Thus they are finite sets. 2 . Infinite set If the number of elements in a set is finite, the set is said to be an infinite set. Thus the set of all natural number is given by  N = { 1, 2, 3, ...}  is an infinite set. Similarly the set of all rational number between ) and 1 given by A = { x:x E Q, 0 <x<1} is an infinite set.

30. Types of Set 3.Null set/ empty set A null set or an empty set is a valid set with no member. 4.Subset A subset  A  is said to be subset of  B  if every elements which belongs to  A  also belongs to  B . A = { 1, 2, 3} B = { 1, 2, 3, 4} A subset of B.

31. Operations on set Union Intersection Difference

32. Formal proof Formal proof- Try to prove the statement B is true because statement A is true Induction on Integers To prove a statement S ( n ) about an integer n by induction, we do: Basis --- show S ( i ) true for a particular basis integer i (0 or 1 usually) Inductive step --- assume n ≥ i (basis integer) , and show that the statement “if S ( n ), then S ( n + 1)” is true.

33. Prove 1+2+...+n=n(n+1)/2 using a proof by induction.

34. Homework Using the principle of mathematical induction, prove that  1)1² + 2² + 3² + ..... + n² = (1/6){n(n + 1)(2n + 1} for all n ∈ N.  2) 1 x 2 + 3 x 4 + 5 x 6 + …. + (2n - 1) x 2n = n(n+1)(4n−1)3 3)1 ∙ 2 + 2 ∙ 3 + 3 ∙ 4 + ..... + n(n + 1) = (1/3){n(n + 1)(n + 2)}.

35. Finite State Machine or Finite Automata A   Finite State Machine , or  FSM , is a computation model that can be used to simulate sequential logic, or, in other words, to represent and control execution flow.  Finite State Machines  can be used to model problems in many fields, including mathematics, artificial intelligence, games or linguistics.

36. Finite State Machine A  Finite State Machine  is any device storing the state of something at a given time. The state will change based on inputs, providing the resulting output for the implemented changes. Finite State Machines  come from a branch of  Computer Science  called “ automata theory ”. The family of data structure belonging to this domain also includes the  Turing Machine The important points here are the following: We have a fixed set of states that the machine can be in The machine can only be in one state at a time A sequence of inputs is sent to the machine Every state has a set of transitions and every tra nsition is associated with an input and pointing to a state

37. Real world examples Coin-operated turnstile States:  locked, unlocked Transitions:  pointing a coin in the slot will unlock the turnstile, pushing the arm of the unlocked turnstile will let the costumer pass and lock the turnstile again Traffic Light States:  Red, Yellow, Green Transitions:  After a given time, Red will change to Green, Green to Yellow, and Yellow to Red

38. FSM

39. Finite-state Automata Finite-state automata are finite-state machines with no output. Finite automata  have two  states , Accept  state  or Reject  state . When the input string is processed successfully, and the  automata  reached its final  state

40. Automata theory Automata is a theoretical branch of computer science and discrete mathematics that focuses on the logic of simple machines. The types of computational models within automata theory include: Finite state machines—Models for any system with a limited number of conditional states of being. Pushdown automata – More complicated than finite state machines, these use regions of memory called stacks to store information as part of a model. Linear-bounded automata (LBA) – Similar to a Turing machine, but the data is limited to a portion of input within a finite group of inputs. Turing machines —The most complex mathematical model within automata theory for testing different input combinations to analyze a larger system or problem. State transition - When a finite state machine switches between states, it is called a  state transition .

41. Finite Automata Finite automata are used to recognize patterns. It takes the string of symbol as input and changes its state accordingly. When the desired symbol is found, then the transition occurs. At the time of transition, the automata can either move to the next state or stay in the same state. Finite automata have two states,  Accept state  or  Reject state . When the input string is processed successfully, and the automata reached its final state, then it will accept. Formal Definition of FA A finite automaton is a collection of 5-tuple (Q, ∑, δ, q0, F), where:

42. Finite Automata Q: finite set of states   ∑: finite set of the input symbol   q0: initial state    F:  final  state   δ: Transition function  

43. Finite Automata Model Finite automata can be represented by input tape and finite control. Input tape:  It is a linear tape having some number of cells. Each input symbol is placed in each cell. Finite control:  The finite control decides the next state on receiving particular input from input tape. The tape reader reads the cells one by one from left to right, and at a time only one input symbol is read.

44. Finite Automata Model

45. FA Types 1. DFA DFA refers to deterministic finite automata. Deterministic refers to the uniqueness of the computation. In the DFA, the machine goes to one state only for a particular input character. DFA does not accept the null move. 2. NFA NFA stands for non-deterministic finite automata. It is used to transmit any number of states for a particular input. It can accept the null move. Some important points about DFA and NFA: Every DFA is NFA, but NFA is not DFA. There can be multiple final states in both NFA and DFA. DFA is used in Lexical Analysis in Compiler. NFA is more of a theoretical concept.

46. Transition Diagram A transition diagram or state transition diagram is a directed graph which can be constructed as follows: There is a node for each state in Q, which is represented by the circle. There is a directed edge from node q to node p labeled a if δ(q, a) = p. In the start state, there is an arrow with no source. Accepting states or final states are indicating by a double circle.

47. Transition Diagram

48. DFA(Deterministic Finite Automata ) A deterministic finite automaton (DFA) consists of 1. a finite set of states (often denoted Q ) 2. a finite set Σ of symbols (alphabet) 3. a transition function that takes as argument a state and a symbol and returns a state (often denoted δ ) 4. a start state often denoted q 0 5. a set of final or accepting states (often denoted F ) We have q 0 ∈ Q and F ⊆ Q

49. Deterministic Finite Automata DFA is mathematically represented as a 5-tuple (Q, Σ, δ, q 0, F ) The transition function δ is a function in Q × Σ → Q Q × Σ is the set of 2-tuples (q, a) with q ∈ Q and a ∈ Σ

50. Regular Language Regular Language : • A language is regular if there exits a DFA for that language . • The language accepted by DFA is RL. Regular Expression: • A Mathematical notation used to describe the regular language. • This is formed by using 3 Symbols: (i). [dot operator] – for concatenation (ii) + [Union operator] –at least 1 occurrence eg ) 1+ = {1,11,111,------- (iii) {*} [Closure Operator ] – Zero or more occurrences eg ) 1* = {Λ ,1,11,111,…..} Basic Regular Expressions: • Ø is a RE and denotes the empty set. • ε is a RE and denotes the set { ε } • For each a in ∑, a is a RE and denotes the set {a} • If r and s are RE that denoting the languages R and S respectively, then, – ( r+s ) is a RE that denotes the set (RUS) – ( r.s ) is a RE that denotes the set R.S – (r)* is a RE that denotes the set R*

51. Graphical Representation of DFA A DFA can be represented by digraphs called state diagram. In which: The state is represented by vertices. The arc labeled with an input character show the transitions. The initial state is marked with an arrow. The final state is denoted by a double circle.

52. DFA-Transition Table,Diagram

53. DFA-Transition Table,Diagram For this example Q = { q 0, q 1, q 2 } start state q 0 F = { q 1 } Σ = { 0, 1 } δ is a function from Q × Σ to Q δ : Q × Σ → Q δ ( q 0, 1) = q 0 δ ( q 0, 0) = q 2

54. Draw a DFA for the language accepting strings ending with ’01’ over input alphabets ∑ = {0, 1} ANS Regular expression for the given language = (0 + 1)*01 Step-01: All strings of the language ends with substring “01”. So, length of substring = 2. Thus, Minimum number of states required in the DFA = 2 + 1 = 3. It suggests that minimized DFA will have 3 states. Step-02: We will construct DFA for the following strings- 01 001 0101 001101

55. Diagram

56. Draw a DFA that accepts a language L over input alphabets ∑ = {0, 1} such that L is the set of all strings starting with ’00 ’. Solution- Regular expression for the given language = 00(0 + 1)* Step-01 : All strings of the language starts with substring “00”. So, length of substring = 2. Thus, Minimum number of states required in the DFA = 2 + 2 = 4. It suggests that minimized DFA will have 4 states. Step-02 : We will construct DFA for the following strings- 00 000 00000

57. Diagram

58. Example 1: Q = {q0, q1, q2}   ∑ = {0, 1}   q0 = {q0}   F = {q2}  

59. Transition Function Example

60. DFA that will accepts the string having odd number of 1's and odd number of 0's

61. Draw a DFA for the language accepting strings ending with ‘ abb ’ over input alphabets ∑ = {a, b} Solution- Regular expression for the given language = (a + b)* abb  S tep-01:  All strings of the language ends with substring “ abb ”. So, length of substring = 3.  Thus, Minimum number of states required in the DFA = 3 + 1 = 4. It suggests that minimized DFA will have 4 states.   Step-02:  We will construct DFA for the following strings- abb aabb ababb abbabb

62. Transition Table States\Input a b ->q0 q1 q0 q1 q1 q2 q2 q1 q3 q3* q1 q0

63. Ex:Language over alphabet {0,1}: The language { 0 n 1 k | n≥1 and k≥1}

64. H.W 1.Design a DFA in which set of all strings can be accepted which ends with ab. ( Given: Input alphabet, Σ={a, b} Language L ={ ab , abab , abaabbab , abbab , bbabaabab ….}) 2. Design a DFA such that: L = { a n b m  | n,m ≥ 0} (Given: Input alphabet, Σ={a, b} Language L = {ε, a, aa , aaa , b, bb, bbb,ab , aab , aaab , abbb , aabb , aaaabbbb , ...})

65. H.W 3.Design a DFA to accept the strings over s={0,1} with three Consecutive Zero 4.Design a DFA to accept the strings over {0,1} With 011 as substring

66. String Acceptance(DFA)

67. H.W 1.Show how the string ω1 =aabba and ω2 =aba is processed 2.Check whether the strings “ababba” ,”baab” are accepted by the DFA?

68. NFA or NDFA(Nondeterministic Finite Automato) NFA refers to Nondeterministic Finite Automaton. A Finite Automata(FA) is said to be non deterministic, if there is more than one possible transition from one state on the same input symbol.  A non deterministic finite automata is also set of five tuples and represented as,  5-tuple (Q, ∑, δ, q0, F), where: Q: finite set of states   ∑: finite set of the input symbol   q0: initial state    F:  final  state   δ: Transition function  

69. NFA Examples An NFA that accepts all binary strings that end with 101.

70. Transition Table 1 A {A} {A,B} B {C} { ∅} C { ∅} {D} D { ∅} { ∅}

71. NFA Examples

72. Design a NFA for the transition table as given below:

73. Design an NFA with ∑ = {0, 1} in which double '1' is followed by double '0'.

74. What is the language accepted by the following finite state automata? a(bb + bba) ∗ ba or ab(bb + bab) ∗ a

75. NFA Examples Give NFAs with the specified number of states recognizing each of the following languages. In all cases, the alphabet is Σ = {0, 1}. The language { w ∈ Σ ∗ | w ends with 00 } with three states

76. Design a NFA to accept strings containing the substring,”0101”.

77. Determine a NFA that accepts L=(aa* (a + b)) .

78. H.W 1.Design a NFA to accept strings over alphabet{0, 1}, such that the third symbol from right end is 0. 2.Design a NFA with no more than five states for the set {ababn : n >= 0}U{aban : n > 0} . 3.Construct a NFA that accepts L={x €{a, b}/ x ends with 'aab‘}

79. String Acceptance By NFA

80. H.W States\Input 1 q0 {q0,q1} q2 q1 {q1,q2} q2 {q2,q0} q1 Check Whether the input String 0100 is Accepted or not

81. H.W States\Input 1 q0 {qo,q3} {q0,q1} q1 q2 q2 q2 q2 q3 q4 q4 q4 q4 Consider the given NFA to Check Whether W=01001 is Valid or Not

82. NFA’s with ε −Transitions We extend the class of NFAs by allowing instantaneous (ε) transitions: 1. The automaton may be allowed to change its state without reading the input symbol. 2. In diagrams, such transitions are depicted by labeling the appropriate arcs with ε. 3. Note that this does not mean that ε has become an input symbol. On the contrary, we assume that the symbol ε does not belong to any alphabet.

83. ε -NFA Example

84. 1.Find the ε-closure of the states 1,2 and 4 in the following transition diagram ε-closure(1)={1,2,3,4,6} ε-closure(2)={2,3,6} ε-closure(4)={4}

85. 1.Find the ε-closure for the following transition diagram ε-closure(A)={A,B,C} ε-closure(B)={B,C} ε-closure(C)={C}

86. H.W Find ε-closure of the all states

87. ε-closure NFA String Acceptance find

88. Conversion from NFA to DFA Steps for converting NFA to DFA: Step 1:  Initially Q' = ϕ Step 2:  Add q0 of NFA to Q'. Then find the transitions from this start state. Step 3:  In Q', find the possible set of states for each input symbol. If this set of states is not in Q', then add it to Q'. Step 4:  In DFA, the final state will be all the states which contain F(final states of NFA)

89. 1.Convert the given NFA to DFA.

90. Now we will obtain δ' transition for state q0. δ'([q0], 0) = [q0]   δ'([q0], 1) = [q1]   The δ' transition for state q1 is obtained as: δ'([q1], 0) = [q1, q2]       ( new  state generated)  δ'([q1], 1) = [q1]   The δ' transition for state q2 is obtained as: δ'([q2], 0) = [q2]   δ'([q2], 1) = [q1, q2]  

91. δ'([q1, q2], 0) = δ(q1, 0) ∪ δ(q2, 0)                         = {q1, q2} ∪ {q2}                         = [q1, q2]   δ'([q1, q2], 1) = δ(q1, 1) ∪ δ(q2, 1)                         = {q1} ∪ {q1, q2}                         = {q1, q2}                         = [q1, q2]   The state [q1, q2] is the final state as well because it contains a final state q2. The transition table for the constructed DFA will be:

92. 0,1

93. H.W Convert NFA TO DFA 1 q0 {q0,q1} {q1} q1 - {q0,q1}