Unit 2 Pumping lemma Unit 2 Pumping lemma

this is about STQA

1. Pushdown Automata and Turing machine

2. 2 P u s hdo w n A ut omat a ( P D A) PDAs: a more powerful computation device that can recognize CFLs. PDA: a є-NFA with a “ stack ” which serves as “memory”, and store a string of stack symbols. The general non-deterministic version accepts ALL CFLs. The deterministic version accepts only a subsets of the CFLs. Regular Languages  Finite State Machines, Regular Expression Context Free Languages  Context Free Grammar, Push-down Automata Regular Languages Context-Free Languages Recursive Languages Recursively Enumerable Languages Non-Recursively Enumerable Languages

3. 3 F or m a l def i n i t i o n o f a P DA M = (Q, Σ, Γ, δ, q , z , F) Q, Σ , q , F a r e th e s am e a s in FSA s . W h ich i s ? Γ: set of stack symbols (finite) (denoted using X, Y, Z) z : start stack symbol.

4. s t a c k 4 tape head stack head finite control t ape P u s hdow n A ut omat a (P D A) The tape is divided into finitely many cells. Each cell contains a symbol in an alphabet Σ . p u s h d o w n T ran s i t i o n s depend s on Current state and Input (these two, the same as FSAs) T o p o f t h e st a c k ( w h i ch i s t h e ne w t h ing) Result: New state. Pop the stack : є And push the stack with new symbol.

5. The stack head always scans the top symbol of the stack. It performs two basic operations: Push : add a new symbol at the top. Pop : read and remove the top symbol. Alphabet of stack symbols: Γ 5 P u s hdow n A ut omat a (P D A ) The head/pointer scans at a cell on the tape and can read a symbol on the cell. In each move, the head can move to the right cell.

6. FINITE AUTOMATA PUSHDOWN AUTOMATA A  finite automaton (FA) is a simple idealized machine used to recognize patterns within input taken from some character set A  pushdown automaton (PDA) is a type of automaton that employs a stack. It doesn’t has the capability to store long sequence of input alphabets It has stack to store the input alphabets Finite Automata can be constructed for Type-3 grammar Pushdown Automata can be constructed for Type-2 grammar Input alphabets are accepted by reaching “final states” Input alphabets are accepted by reaching : 1.      Empty stack 2.      Final state NFA can be converted into equivalent DFA NPDA has more capability than DPDA It consist of 5 tuples : L = {Q, q , ∑, F, σ} It consists of 7 tuples : L = {Q, q , ∑, F, ᴦ, σ, z  } Finite automata can be constructed for regular language Pushdown automata can be constructed for context free language

7. 7 P u s hdow n A ut oma t o n ( P D A ) In on e t r ansi t i o n t h e P D A ma y d o t h e f o l lo w i ng: Consume the input symbol. If є is the input symbol, then no input is consumed. Go to a new state, which may be the same as the previous state. Replace the symbol at the top of the stack by any string. If this string is є then this is a pop of the stack The string might be the same as the current stack top (does nothing ) Replace with a new string ( pop and push ) Replace with multiple symbols (multiple pushes )

8. 8 T w o d i f f eren t k i n d o f P D A s E m p t y s t a ck P D A : Sometimes, it is easier to design a PDA that accepts if and only if it is capable of having an empty stack. Final state PDA. If there is a PDA P that accepts a language by final state, then there is another PDA P' that accepts the same language by empty stack. Normally P ≠ P'

9. Example: PDA for L = { 0 n 1 n | n 0 } Design by Emptying stack: The PDA first pushes “ $ 0 n ” on stack. Then, while reading the 1 n string, the zeros are popped again. If, in the end, $ is left on stack, then “accept” q 1 q 3 q 2 q 4  ,  $  , $  1, 0  1, 0  0, $ 0

10. Machine Diagram for 0 n 1 n q 1 q 3 q 2 q 4  ,  $  , $  1, 0  1, 0  0,  0 On w = 000111 (state; stack) evolution: (q 1 ;  )  (q 2 ; $ )  (q 2 ; 0 $ )  (q 2 ; 00 $ ) (q 2 ; 000 $ )  (q 3 ; 00 $ )  (q 3 ; 0 $ )  (q 3 ; $ ) (q 4 ;  ) This final q 4 is an accepting state

11. One more PDA – for even length palindromes L = { w w R | w is in {0, 1}* }

12. Example:  Define the pushdown automata for language { a n b n | n  0} using final state. Solution:  M = where Q = {q0, q1, q2, q3} and ∑ = {a, b} and Γ = { A, Z } and F={q3} and δ is given by: δ( q0, a, Z ) = { ( q1, AZ ) } δ( q1, a, A) = { ( q1, AA ) } δ( q1, b, A) = { ( q2, ɛ) } δ( q2, b, A) = { ( q2, ɛ) } δ( q2, ɛ, Z) = { ( q3, Z) } Let us see how this automata works for aaabbb :

13. Explanation:   Initially, the state of automata is q0 and symbol on stack is Z and the input is aaabbb as shown in row 0. On reading a (shown in bold in row 1), the state will be changed to q1 and it will push symbol A on stack. On next a (shown in row 2), it will push another symbol A on stack and remain in state q1. After reading 3 a’s, the stack will be AAAZ with A on the top. After reading b (as shown in row 4), it will pop A and move to state q2 and stack will be AAZ. When all b’s are read, the state will be q2 and stack will be Z. In row 7, on input symbol ɛ and Z on stack, it will move to q3. As final state q3 has been reached after processing input, the string will be accepted. This type of acceptance is known as  acceptance by final state .

14. 36 Є,zoF → z0F Translation between Empty Stack PDA to Final State PDA. ● Let Pv be a PDA that accepts by empty stack. Pv = (Q, Σ , Γ, δ, q , z ) Then, we define Pf = (Q U {q0F, qF }, Σ , Γ U {z0F}, δF , q , z , { qF }) that accepts by final state the same strings as Pv by empty stack. ● q0F q qq F F Є,zoF → z0z0F

15. PDAs versus CFL Theorem 2.20 : A language L is context-free if and only if there is a pushdown automata M that recognizes L. General construction: each rule of CFG A  w is included in the PDA’s move. Rule 1: Non terminal on top of stack – match stack top of a rule and pop stack and push right Hand side rule onto stack Rule 2: Look at input See input scanned and top of stack element if both match, pop top stack element and advance input to next one Input not advanced Match top of stack Push to stack

16. Equivalence of PDA and CFG Part 1: For every CFG, we can build an equivalent PDA.

17. A Turing Machine is an accepting device which accepts recursively enumerable languages generated by type 0 grammars. It was invented in 1936 by Alan Turing. Despite its simplicity, the  machine  can simulate ANY computer algorithm, no matter how complicated it is! . A  Turing machine  is a mathematical model of computation that defines an abstract  machine. A  Turing machine  is a system of rules, states and transitions rather than a real  machine . Purposes for a  Turing machine : deciding formal languages and solving mathematical functions. 

18. 22 Start Finish final state initial state The 0 is the delimiter that separates the two numbers The 0 here helps when we use the result for other operations

19. 23 Turing machine for function

20. 24 Execution Example: Time 0 Final Result (=2) (=2)

21. 25 Time 0

22. 26 Time 1

23. 27 Time 2

24. 28 Time 3

25. 29 Time 4

26. 30 Time 5

27. 31 Time 6

28. 32 Time 7

29. 33 Time 8

30. 34 Time 9

31. 35 Time 10

32. 36 Time 11

33. 37 HALT & accept Time 12

34. Draw a Turing machine which subtract two numbers. F( m,n ) ={m n , m-n case 1 {m≤ n, 0 case 2 Steps: 1.  If 1(m side) found convert 1 into B and go right then keep all 1’s no change and go right. 2.  Skip 0 and all 1’s(n side) as same and go right if B found move left convert first 1’s of n side as B and go left. 3.  Skip all 1’s and 0 with no changes move left. 4.   When B of m side found move right with no changes (seems that one changes of m,n done). 5. Repeat the same from step 1. 6. From moving left of n side after B if 0 is found instead of 1 then convert 0 as 1 and move left and halt in accepting state. 7. In step 4, when moving right instead of 1 if 0is found change to B and move right. 8. Convert all 1’s as B and move right, if B found keep no changes move right and go to accept state

35. Decidable and Undecidable A problem P is decidable if it can be solved by a Turing machine T that always halt. (We say that P has an effective algorithm.) Note that the corresponding language of a decidable problem is recursive . A problem is undecidable if it cannot be solved by any Turing machine that halts on all inputs. Note that the corresponding language of an undecidable problem is non-recursive.

36. Complements of Recursive Languages Theorem : If L is a recursive language, L is also recursive. Proof : Let M be a TM for L that always halt. We can construct another TM M from M for L that always halts as follows: Accept Reject Accept Reject M M Input

37. Complements of RE Languages Theorem : If both a language L and its complement L are RE, L is recursive. Proof : Let M 1 and M 2 be TM for L and L respectively. We can construct a TM M from M 1 and M 2 for L that always halt as follows: Accept Accept Accept Reject M 1 M Input M 2

38. Multi-Tape Turing Machines A multi-tape Turing machine is one that has n tapes for reading and writing information, instead of only one. The first tape is initialized with the input, and the rest are initially empty. Despite these added abilities, multi-tape Turing machines are no more capable than regular ones. Store the contents of all n tapes on the one tape, separated by the # symbol. Keep track of the tape heads using “dotted symbols”. Each of these is a new input symbol which is identical to a symbol, with a dot over it. Have the machine execute the tape operations of the multi-tape machine one by one.

39. Modified Post Correspondence Problem We have seen an undecidable problem, that is, given a Turing machine M and an input w, determine whether M will accept w (universal language problem). We will study another undecidable problem that is not related to Turing machine directly. Given two lists A and B: A = w 1 , w 2 , …, w k B = x 1 , x 2 , …, x k The problem is to determine if there is a sequence of one or more integers i 1 , i 2 , …, i m such that: w 1 w i 1 w i 2 … w i m = x 1 x i 1 x i 2 … x i m ( w i , x i ) is called a corresponding pair.

40. Example A B i 1 2 3 w i 1 0111 10 x i 111 10 This MPCP instance has a solution: 1,3, 2, 2, 4: w 1 w 3 w 2 w 2 w 4 = x 1 x 3 x 2 x 2 x 4 = 1101111110 4 11 1

41. Class Discussion A B i 1 2 3 w i 10 011 101 x i 101 11 011 Does this MPCP instance have a solution?