Formal language and automata theoryLAT Class notes.pptx

FLAT NOTES theory of computation

1. Automata Classified into 3 types 1. Finite Automata 2. Push Down Automata 3. Turing Machine With OUT PUT WITHOUT OUTPUT 1. MOORE MACHINE 2. MELAY MACHINE 1. Deterministic Finite Automata 2. Non Deterministic Finite Automata 3. Non Deterministic finite automata with epsilon moves 

2. Applications of Finite Automata. Finite Automata  ' A finite automaton is a mathematical model consisting of states, input symbols, and a transition function. It reads input symbols and transitions between states based on the transition function, either accepting or rejecting the input. It's used to model and analyze systems with a finite number of states in various fields. Some applications of finite automata are as follows: It have various applications lexical analysis, passing pattern matching and creat e compilers Recognizing patterns in text or other data:  Finite automata can be used to search for and recognize specific patterns in text or other data. For example, a finite automaton can be used to recognize email addresses, URLs, or phone numbers in text. This is commonly used in text processing software, such as search engines or spam filters. Implementing regular expressions in programming languages:  Regular expressions are a way to describe patterns in text using a set of rules. These rules can be translated into a finite automaton, which is used to match the pattern in the input text. Many programming languages, such as Perl, Python, and Java, use finite automata to implement regular expressions. Validating input in form fields on websites:  Finite automata can be used to validate user input in form fields on websites. For example, a finite automaton can be used to ensure that a user enters a valid email address or password that meets certain criteria, such as length or character requirements.

3. 5. Modeling digital circuits and switching systems:  Finite automata can be used to model digital circuits and switching systems, such as those found in computers and other electronic devices. This can help engineers design and optimize these systems for maximum efficiency and performance. 6. Designing and analyzing computer algorithms and programs:  Finite automata can be used to design and analyze computer algorithms and programs. They can help programmers understand the behavior of the program and identify potential errors or inefficiencies. 7. Building compilers and interpreters:  Finite automata are used in the development of compilers and interpreters, which are programs that translate high-level programming languages into machine code that can be executed by a computer. Finite automata are used to recognize and process the syntax and semantics of the programming language. 8. Analyzing the behavior of software and hardware systems:  Finite automata can be used to analyze the behavior of software and hardware systems, such as operating systems or network protocols. They can help identify bugs or vulnerabilities in the system and optimize its performance.

4. 9. Verifying the correctness of software and hardware systems:  Finite automata can be used to verify the correctness of software and hardware systems by checking whether they satisfy certain requirements or specifications. 10. Developing language models and machine learning algorithms:  Finite automata are used in the development of language models and machine learning algorithms, which are used in natural language processing and other applications. They can help identify patterns in data and make predictions based on those patterns. 11. Studying formal languages and their properties:  Finite automata are used in the study of formal languages and their properties. They can help identify the structure and rules of different types of languages and the limitations of those languages in terms of expressiveness and complexity.

5. DFA (Deterministic finite automata) DFA refers to deterministic finite automata. Deterministic refers to the uniqueness of the computation. The finite automata are called deterministic finite automata if the machine is read an input string one symbol at a time. In DFA, there is only one path for specific input from the current state to the next state. DFA does not accept the null move, i.e., the DFA cannot change state without any input character. DFA can contain multiple final states. It is used in Lexical Analysis in Compiler. In the following diagram, we can see that from state q0 for input a, there is only one path which is going to q1. Similarly, from q0, there is only one path for input b going to q2.

6. Formal Definition of DFA A DFA is a collection of 5-tuples same as we described in the definition of FA. Q: finite set of states   ∑: finite set of the input symbol   q0: initial state    F:  final  state   δ: Transition function   Transition function can be defined as: δ:  Q x ∑→Q  

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

8. Example 1: Q = {q0, q1, q2}   ∑ = { ,  1 }   q0 = {q0}   F = {q2}         Transition Diagram:                                 

9. Present State Next state for Input 0 Next State of Input 1 →q0 q0 q1 q1 q2 q1 *q2 q2 q2 Transition Table:

10. Example 2: DFA with ∑ = {0, 1} accepts all starting with 0.       Explanation: In the above diagram, we can see that on given 0 as input to DFA in state q0 the DFA changes state to q1 and always go to final state q1 on starting input 0. It can accept 00, 01, 000, 001....etc. It can't accept any string which starts with 1, because it will never go to final state on a string starting with 1.    

11. Example 3: DFA with ∑ = {0, 1} accepts all ending with 0. Solution: Explanation: In the above diagram, we can see that on given 0 as input to DFA in state q0, the DFA changes state to q1. It can accept any string which ends with 0 like 00, 10, 110, 100....etc. It can't accept any string which ends with 1, because it will never go to the final state q1 on 1 input, so the string ending with 1, will not be accepted or will be rejected.

12. NFA (Non-Deterministic finite automata) NFA stands for non-deterministic finite automata. It is easy to construct an NFA than DFA for a given regular language. The finite automata are called NFA when there exist many paths for specific input from the current state to the next state. Every NFA is not DFA, but each NFA can be translated into DFA. NFA is defined in the same way as DFA but with the following two exceptions, it contains multiple next states, and it contains ε transition.

13. Problem 1: Design the NFA of all binary strings Q = {q0, q1, q2}   ∑ = { ,  1 }   =QX ∑  q0 = {q0}   F = {q2}     Q 1   1  

14. In the following image, we can see that from state q0 for input a, there are two next states q1 and q2, similarly, from q0 for input b, the next states are q0 and q1. Thus it is not fixed or determined that with a particular input where to go next. Hence this FA is called non-deterministic finite automata.

15. Formal definition of NFA NFA also has five states same as DFA, but with different transition function, as shown follows : δ: Q x ∑ →2 Q where, Q: finite set of states   ∑: finite set of the input symbol   q0: initial state    F:  final  state   δ: Transition function  

16. Graphical Representation of an NFA An NFA 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 the double circle.

17. Example 1: Find Transition table for the following Q = {q0, q1, q2}   ∑ = { ,  1 }   q0 = {q0}   F = {q2}   Solution: Transition diagram: Given Trasition Diagram

18. Transition Table: Present State Next state for Input 0 Next State of Input 1 →q0 q0, q1 q1 q1 q2 q0 *q2 q2 q1, q2 In the above diagram, we can see that when the current state is q0, on input 0, the next state will be q0 or q1, and on 1 input the next state will be q1. When the current state is q1, on input 0 the next state will be q2 and on 1 input, the next state will be q0. When the current state is q2, on 0 input the next state is q2, and on 1 input the next state will be q1 or q2.

19. Example 2: NFA with ∑ = {0, 1} accepts all strings with 01. Transition Diagram : Transition Table: Present State Next state for Input 0 Next State of Input 1 →q0 q1 ε q1 ε q2 *q2 q2 q2

20. Example 3: NFA with ∑ = {0, 1} and accept all string of length atleast 2. Transition Diagram : Transition Table: Present State Next state for Input 0 Next State of Input 1 →q0 q1 q1 q1 q2 q2 *q2 ε ε

21. Problems related to of NFA Problem 1: Design a NFA for the transition table as given below: Present State 1 →q0 q0, q1 q0, q2 q1 q3 ε q2 q2, q3 q3 →q3 q3 q3 Solution: Given Data is that The transition diagram can be drawn by using the mapping function as given in the table.

22. Here,        δ( q0,  ) = {q0, q1}          δ( q0,  1 ) = {q0, q2}   Then,  δ( q1,  ) = {q3}   Then,  δ( q2,  ) = {q2, q3}          δ( q2,  1 ) = {q3}   Then,  δ( q3,  ) = {q3}          δ( q3,  1 ) = {q3}  

23. Problems related to of NFA Problem 2 : Design an NFA with ∑ = {0, 1} accepts all string ending with 01. Hence, NFA would be:

24. Present State 1 →q0 q0, q1 q0 q1 ε q2 q2 ε ε

25. DFAs NFA DFA stands for Deterministic Finite Automata . NFA stands for Nondeterministic Finite Automata . For each symbolic representation of the alphabet, there is only one state transition in DFA. No need to specify how does the NFA react according to some symbol. DFA cannot use Empty String transition. NFA can use Empty String transition. DFA can be understood as one machine. NFA can be understood as multiple little machines computing at the same time. In DFA, the next possible state is distinctly set. In NFA, each pair of state and input symbol can have many possible next states. DFA is more difficult to construct. NFA is easier to construct. DFA rejects the string in case it terminates in a state that is different from the accepting state. NFA rejects the string in the event of all branches dying or refusing the string. δ: QxΣ -> Q i.e. next possible state belongs to Q. δ: Qx (Σ U ε) -> 2^Q i.e. next possible state belongs to power set of Q. Backtracking is allowed in DFA. Backtracking is not always possible in NFA. Conversion of Regular expression to DFA is difficult.  Conversion of Regular expression to NFA is simpler compared to DFA.   Epsilon move is not allowed in DFA Epsilon move is allowed in NFA DFA allows only one move for single input alphabet. There can be choice (more than one move)  for single input alphabet. Difference between DFA and NFA : 

26. MOORE MACHINE Moore machine is a finite state machine in which the next state is decided by the current state and current input symbol. The output symbol at a given time depends only on the present state of the machine. Moore machine can be described by 6 tuples (Q, q0, ∑, , δ, λ) where, Mathematical machine M= (Q, q0, ∑, , δ, λ) Q: finite set of states   q0: initial state of machine   ∑: finite set of input symbols   : output alphabet   δ: transition function where Q × ∑ → Q   λ: output function where Q → O    

27. It is an Automata which produces an output depends on the state of the MACHINE 6- Tuples M= (Q, q0, ∑, , δ, λ)  

28. Example 1: The state diagram for Moore Machine is given below find the Sequence of States for the given STRING W=1001

29. Initially we need to start with  that is A(1001) A starting a #(A, )=a A to B is 1 b #(A, B)=b B to B is 0 b #(B, B)=b B to B is 0 b #(B, B)=b B to B is 1 c #(B, C)=c The required sequence of states are A B B B C=a b b b c .

30. Mealy Machine A Mealy machine is a machine in which output symbol depends upon the present input symbol and present state of the machine. In the Mealy machine, the output is represented with each input symbol for each state separated by /. The Mealy machine can be described by 6 tuples (Q, q0, ∑, O, δ, λ') where Q: finite set of states   q0: initial state of machine   ∑: finite set of input alphabet   : output alphabet   δ: transition function where Q × ∑ → Q   λ': output function where Q × ∑ →     

31. Example 1: The state diagram for Mealy Machine is given below find the Sequence of States for the given STRING W=1001

32. Initially we need to start with  that is (1001) starting q0 to q1 n #(q0, q1)=n q1 to q1 0 y #(q1, q1)=y q2 to q1 0 n #(q1, q2)=n q0 to q2 1 y #(q0, q2)=y q1 to q2 1 n #(q1, q2)=n q2 to q2 1 y #(q2, q2)=y The required sequence of states are

33. The difference between Moore Machine Mealy Machine   Output depends only upon the present state.  Output depends on the present state as well as present input.  Moore machine also places its output on the transition. Mealy Machine places its output on the transition. More states are required.  Less number of states are required.   There is less hardware requirement for circuit implementation.  There is more hardware requirement for circuit implementation.   They react slower to inputs(One clock cycle later).  They react faster to inputs.   Synchronous output and state generation.  Asynchronous output generation.   Output is placed on states.  Output is placed on transitions.   Easy to design.  It is difficult to design.  If input changes, output does not change If input changes, output also changes. Has more or the same states as that of the Mealy machine. Has fewer or the same states as that of the Moore machine.

34. Minimization of DFA(Equivalence method) Eliminate all dead states and in accessible states Draw a transition table Applying equivalence theorem Repeated up to no changes All those states which belong to the same set are equivalent are equal

35. Prob 1. Find the Minimization of DFA for the following Transition Diagram. Solution: Given Data is that

36. Based on the procedure of Equivalence theorem Step 1: Eliminate all the dead states and in accessible states. From the above fig.each and every state connected properly, so No inaccessible states &No DEAD STATES Step2:Prepare State Transistion Table for the above FIG,

37. 1 A(Initial State) B C B B D C B C D B E E(Final State) B C

38. Step 3: separate it Final state and Non Final states as Groups. -{A,B,C,D} {E} # Non Final State & Final State. -{A,B,C} {D} {E} -{A,C} {B} {D} {E} -{A,C} {B} {D} {E}Steps are repeated Stop the process Step 4:Prepare Transition Diagram for ABOVE Steps

39. The Required OUTPUT Transition Diagram is

40. Regular expression A Regular expression describes a language exclusively by means of a single symbol and empty  Two symbols are combinly/together used U/Union and * with ( , ) q* is a regular expression alphabet  U {( , ), U ,* , }

41. (AUTONOMOUS) Affiliated to JNTUH , Approved by AICTE , Accredited by NAAC with A++ Grade, ISO 9001:2015 Certified Kacharam, Shamshabad, Hyderabad – 501218, Telangana, India DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING II B. TECH II SEMESTER 2023-2024 A8515- Formal Languages and Automata Theory Course Plan Course Outcomes (COs) After the completion of the course, the learner will be able to: CO# CO Statement BL# CO1 Interpret the core concepts of automata theory to design finite automata for given formal languages. L3 CO2 Identify the relationship between formal languages, automata and regular expression. L3 CO3 Write and simplify context free grammars for formal languages. L3 CO4 Construct push down automata for various formal language constructs. L3 CO5 Model turing machine to recognize formal languages and computational operations. L3 Course Plan Session # Lecture/ Practice # Topic BL# CO# 1 L1 FINITE AUTOMATA (FA): Introduction, model and behavior L2 CO1 2 L2 Deterministic Finite Automata (DFA) -Formal definition, simpler notations (state transition diagram, transition table) L2 CO1 3 L3 language of a DFA L3 CO1 4 L4 Nondeterministic Finite Automata (NFA)-definition of NFA, language of an NFA L2, L3 CO1 5 L5 Equivalence of Deterministic and Nondeterministic Finite Automata L2 CO1 6 L6 Applications of Finite Automata L3 CO1 7 L7 Finite Automata with Epsilon Transitions, L2 CO1 8 L8 Eliminating epsilon transitions L3 CO1 9 L9 Minimization of Deterministic Finite Automata L3 CO1 10 L10 Examples Minimization of Deterministic Finite Automata L3 CO1 11 L11 Finite automata with output (Moore and Mealy machines). L2, L3 CO1 12 L12 Examples Finite automata with output (Moore and Mealy machines). L3 CO1 13 L13 REGULAR EXPRESSIONS (RE): Introduction, algebraic laws for Regular Expressions L2 CO2 Page 45 of 2

42. Page 46 of 2 14 L14 Finite Automata and Regular Expressions L3 CO2 15 L15 from DFA’s to Regular Expressions L3 CO2 16 L16 converting Regular Expressions to Automata L3 CO2 17 L17 Applications of Regular Expressions. L3 CO2 18 L18 Proving languages to be non-regular -Pumping lemma, applications. L2 CO2 19 L19 Closure properties of regular languages. L2 CO2 20 L20 CONTEXTFREE GRAMMARS (CFG): Formal definition, sentential forms L2 CO3 21 L21 leftmost and rightmost derivations, the language of a CFG L3 CO3 22 L22 Derivation tree or parse tree, Ambiguous Grammar. L3 CO3 23 L23 Simplification of CFG: Removing useless symbols, Null (epsilon) –productions and unit productions. L3 CO3 24 L24 Simplification of CFG:, Null (epsilon) –productions L3 CO3 25 L25 Simplification of CFG: unit productions. L3 CO3 26 L26 Normal forms – CNF L2, L3 CO3 27 L27 Normal forms –GNF. L2, L3 CO3 28 L28 Proving that some languages are not context free - Pumping lemma for CFLs L3 CO3 29 L29 Pumping Lemma applications. L3 CO3 30 L30 Closure properties of CFLs. L2 CO3 31 L31 PUSHDOWN AUTOMATA (PDA): Definition of the Pushdown Automata, L2 CO4 32 L32 the languages of PDA (acceptance by final state and empty stack), L3 CO4 33 L33 Equivalence of PDA’s and CFG’s L2 CO4 34 L34 CFG to Pushdown Automata L3 CO4 35 L35 Examples CFG to Pushdown Automata L3 CO4 36 L36 Pushdown Automata to CFG L3 CO4 37 L37 Examples Pushdown Automata to CFG L3 CO4 38 L38 Deterministic PDA. L3 CO4 39 L39 TURING MACHINES (TM): Formal definition and behavior L2, L3 CO5 40 L40 languages of a TM, TM Acceptors L2, L3 CO5 41 L41 TM as accepters L3 CO5 42 L42 TM for computable functions L3 CO5 43 L43 Types of TMs. L2 CO5 44 L44 Chomsky Hierarchy L2 CO5 45 L45 Post Correspondence Problem L3 CO5 Name of the Course Lead: Mr. C. Satya Kumar Signature of the Course Lead:

43. Regular expression (RE) is defined as ∈(Epsilon is a Regular expression then the corresponding to the language L{∈}=0  is regular expression corresponding to the language L={ } x is Regular expression corresponding to the language L={x} If x is a regular expression over a language L(x) If y is a regular expression over a language L(y) The main three conditions for Language (x + y) is a regular expression corresponding to language L(x)  L(y) where L(x  y)= L(x)  L(y) 2. XY is a regular expression corresponding to L(x) . L(y) where L( x.y )= L(x) . L(y) 3. R* is a regular expression corresponding to L(R*)=(L(R)*)

44. Regular language  is a language that can be defined by  NFA  NFA with ∈ DFA Regular Expression Examples of Regular expressions: Regular expression denoting the language with strings having any number of a’s RE=a* 2. Regular expression denoting the language with strings having any number of a’s and b’s RE=( a+b )*

45. 3. Regular expression denoting the language start with the strings a’ and end with b’s RE=a( a+b )*b 4. All the strings of 0’s and 1’s L={ ∈,0,1,01,10,000,110…etc} Regular expression RE=(0+1)* 5. All the strings of 0’s and 1’s and ends with “00” L={00 ,0100 ,100,0100,100,000,1100…etc} Regular expression RE=(0+1)*00

46. I dentities for regular expression – There are many identities for the regular expression. Let p, q and r are regular expressions . ∅ + r = r ∅.r= r.∅ = ∅ ∈.r = r.∈ =r 4. ∈* = ∈ and ∅* = ∈ 5. r + r = r 6. r*.r* = r* and 7. r.r * = r*.r = r * . 8. (r*)*  =  r* 9.∈ + r.r * = r* = ∈ + r.r * 10.( p+q )* p=p( q+p )* 11. ( p.q )*.p = p.( q.p )* 12. (p + q)* = (p*.q*)* = (p* + q*)* 13. (p+ q).r= p.r + q.r and r.( p+q ) = r.p + r.q

47. I dentities for regular expression – There are many identities for the regular expression. Let p, q and r are regular expressions. ∅ + r = r ∅.r= r.∅ = ∅ ∈.r = r.∈ =r 4. ∈* = ∈ and ∅* = ∈ 5. r + r = r 6. r*.r* = r* 7. r.r * = r*.r = r * . 8. (r*)*  =  r* 9.∈ + r.r * = r* = ∈ + r.r * 10.( p+q )* p=p( q+p )* 11. ( p.q )*.p = p.( q.p )* 12. (p + q)* = (p*.q*)* = (p* + q*)* 13. (p+ q).r= p.r + q.r and r.( p+q ) = r.p + r.q

48. Ardens Theorem : If P does not contains ∈ (here ∈  p) then the following equations are   r= q p *

50.  And each number of  is a regular expression If  and  are regular expressions then(  U  ) is also a Regular expression If  and  are regular expressions then .  Is also regular expression Note.1: If  is any regular expression then L() is the Language. L is denoted as L( ={} ) and L(a)=a for all a belongs to  If  and  are regular expressions then L(, )=L( ). L( ) If  is a regular expressions then L( )= L(   Operations on Regular Language

51. Accepting of a string and Not accepting of a string     The various operations on regular language are: Union:  If L and M are two regular languages then their union L U M is also a union. 1 . L U M = {s | s is in L or s is in M}   Intersection:  If L and M are two regular languages then their intersection is also an intersection. 1 . L ⋂ M = { st  | s is in L and t is in M}  

52. Example 1: Write the regular expression for the language accepting all combinations of a's, over the set ∑ = {a} Solution: All combinations of a's means a may be zero, single, double and so on. If a is appearing zero times, that means a null string. That is we expect the set of {ε, a, aa, aaa , ....}. So we give a regular expression for this as: R = a*   That is Kleen closure of a.

53. Example 2: Write the regular expression for the language accepting all combinations of a's except the null string, over the set ∑ = {a} Solution: The regular expression has to be built for the language L = {a, aa,  aaa , ....}   This set indicates that there is no null string. So we can denote regular expression as: R = a +

54. Example 3: Write the regular expression for the language accepting all the string containing any number of a's and b's. Solution: The regular expression will be: r.e . = (a + b)*   This will give the set as L = {ε, a, aa, b, bb, ab, ba, aba, bab , .....}, any combination of a and b. The (a + b)* shows any combination with a and b even a null string.

55. Conversion of Finite Automata to Regular Expression Procedure: Step 1:Identify all the incoming edges for each state along with weightage and write in equation format Step2:For initial state add ∈ Step 3: Calculate all the equations Step 4: Result is the value of final state.

56. Problem 2: Conversion of Finite Automata to Regular expression by using Arden's Theorem

57. Problem 3: Conversion of Finite Automata to Regular expression by using Arden's Theorem

58. Note: In theoretical computer science and formal language theory, a regular language is  a formal language that can be defined by a regular expression , .. Pumping Lemma: It’s generating many sub strings from a given string Pumping lemma is used to prove given languages are not regular If given language(L) is regular it satisfies the pumping lemma If given language(L)is not regular it does not satisfies the pumping lemma.

59. Theorem: Statement: Let M ═(Q,∑, δ, q0,f) be a finite automata with n states. Let L be a regular set accepted by a finite automata. Let W ∈ L(W belongs to L) and ǀwǀ =m if m≥n then there exist x,y,z such that w= x.y.z , ǀyǀ > 0 And Belongs to L(m)

60. Other words: The Pumping lemma for regular languages : For showing certain languages NOT to be regular Statement: Let L be a regular language then there exist a constant n such that for every string w in L, IwI ≥ n we break w into 3strings w=xyz such that 1. y not equal to epsilon (y≠ ∈ ) 2.IxyI less than are equal to n 3. for all i ≥ 0 the string x (y power i )z is also in language L Ex: n=3 w= abc we need 4 states w= abcb or abbc or aabc etc..but it is wrong.so we need to write x (y power i )z

61. To prove it’s not regular Assume L is regular So pumping lemma hold for L It’s have a pumping length (m) All strings longer that (m) can be pumped IwI >=m Find a string w in L such that IwI >=m Divide w into xyz Show that Does not belongs to L for some ‘ i ’ 8.Consider all ways w can be divided into xyz 9. In this case not all 3 pumping conditions satisfied

62. 10. W cannot be pumped (contradiction) That is All the 3 conditions must satisfy 1. must be in given language L 2.IyI>0 each of y>0 3. IxyI≤m here m is pumping length. Pumping lemma is necessity condition for regularity of given language L,If given language is regular then there exist a constant p such that,any string in s in the language with IsI p can be divided into 3 parts s= xyz where all 3 conditions should satisfy.  

63. Pumping lemma with example: problem1: Note: The Pumping Lemma is a necessary condition for regularity. It states that if a language is regular, then there exists a constant p such that any string s in the language with |s|≥p can be divided into three parts: s = xyz, where | xy |≤p, |y|≥1, and for all i≥0, x z ∈ L. x z belongs to Language L.  

64. problem1: Prove that problem2: Prove that problem3: Prove that By using Pumping Lemma.  

65. Problem1: Prove that Sol :Given data is that We have to prove the given language is NOT REGULAR Let P= Assume tat the given Language is REGULAR According to Pumping Lemma Where 1. | xy |≤p,(here p is constant ,we can take some times n,m etc..) 2. |y|≥1, 3. x z ∈ L. and for all i≥0, x z belongs to Language L.  

66. Let n=5 String s= xyz [since here IwI =m string size] P= P= aaaaa bbbbb ccccc since m=5 Case i . Given string convert/spilt into xyz xy z That is x z The y in ‘a’ part aa aaa bbbbb ccccc x y z Case 2.y in b part aaaaa bb bbb ccccc x y z  

67. Case 3.y in c part aaaaa bbbbb ccc cc X y z Case 4.y in abc part aaa aabbbbbccc cc X y z now we need to check condition x z ∈ L. and for all i≥0, NOW i =2 case 1. x z aaaaabb bbbbbb ccccc X y z a=5 b=8 c=5 NOT EQUAL  

68. x z ∈ L. and for all i≥0, NOW i =2 case 2. x z aaaaabb bbbbbb ccccc X y z a=5 b=8 c=5 NOT EQUAL NOW i =2 case 3. x z aaaaabbbbb cccccc cc X y z a=5 b=5 c=8 NOT EQUAL  

69. NOW we need to check condition 2 that is | xy |≤p, here p=n=5 case 1. aa aaa bbbbb ccccc x y z | xy |=5 ≤p True Case 2. aaaaabb bbb ccccc X y z | xy |= 10≤=5 ≤p False Case 3 aaaaa bbbbb ccc ccc X y z | xy |= 13≤=5 ≤p False Case 4: aaa aabbbbbcc ccc X y z | xy |= 12≤=5 ≤p False

70. Problem2: Prove that Sol :Given data is that We have to prove the given language is NOT REGULAR Let P= Assume tat the given Language is REGULAR let L be the constant let w= xyz such that |y|≥1 | xy |≤n or p(here n=p), x z ∈ L. and for all i≥0, x z belongs to Language L. Constructing a DFA Let n=2 w=0011 here x=0 y=0 z=11 assume that i =2 x z ∈ L. and for all i≥0, that is x z x z=00011 Language L This is contradiction hence given language is NOT REGULAR  

71. Problem3: Prove that Sol :Given data is that We have to prove the given language is NOT REGULAR Let P= Assume tat the given Language is REGULAR let L be the constant let w= xyz such that |y|≥1 | xy |≤n or p(here n=p), x z ∈ L. and for all i≥0, x z belongs to Language L. Let w= (n nor of ‘a’s followed by atleast “n+1” b’s Constructing a DFA Let n=2 w= here x=a y=a z=bb assume that i =2 x z ∈ L. and for all i≥0, that is x z x z=a Language L( number of a’ are more than b’s) This is contradiction hence given language is NOT REGULAR  

72. Unit III Context free Grammar: It is a finite set of variables (Non Terminal) each of which represents a part of the language. Def: It is represented by variables described recursively in symbols called as terminals. Mathematical definitions: 4 tuples G=(V,T,P,S) # is called Grammar here V=Variables T=Terminals P=productions S=Special symbols

73. Capital letters A,B,C,D.. Etc . –Variables S=Special Strings Lower case letters (Greek letters also- ,,..etc), a,b,c,d are TERMINALS

74. Special Greek letters ,,      One string to one string –Derivation One production to one production   (since one production) Represented from  to . Derivation Tree/Parse Tree Grtaphical representation of the given Grammar.

75. Right Most Derivation(RMD) Root vertex Left Most Derivation(LMD) Note: Must be labelled by start symbol with * Vertex –Labelled by non Terminals Leaves –Labelled by Terminals or ∈

76. RMD & LMD Production 1 S →0B/1A A →0/0S/1AA } w=00110101 B →1/1S/0BB LMD S →0B →00BB (B →0BB) → 001SB (B → 1S) →0011AB (S →1A) →00110SB (A →0S) →001101AB (S → 1A) →0011010B (A →0) → 00110101 (B → 1)

77. RMD Production 1 S →0B/1A A →0/0S/1AA } w=00110101 B →1/1S/0BB LMD S →0B →00BB (B →0BB) → 00B1 (B → 1) →001S1 ( B →1S) →0011A1 (S →1A) →00110S1 ( A →0S ) →001101A1 (S →1A) → 00110101 (A →0 )

78. A language L is context free if it is L(G) for some context-free grammar G . that u = xAy , v = xwy , and A →G w. That is, u ⇒ v means v can be obtained from u by using a rule A →G w and replacing an occurrence of A in u by w to obtain v. G, possibly no replacements, possibly one or more replacements

79. Example: Construct CFG with accept the strings having at least 2 a’s over the ={a,b} Sol :Given data is that We have to construct the grammar as per the above condition Let us consider the regular expression= (a + b)*  a (a + b)*  a (a + b)* [since at least 2 a’s ] Let us consider the production rule S  T a T a T T  aT/bT/ To construct the grammar Let us consider S  T a T a T Replace the T values with aT or bT or   

80. Now T with bT  S  bTa bT a bT Now T with  S  b  a b  a b {since T=T or a=a….etc) S  b  a b  a b  S  b a b a b This is the required context free grammar with accepting the strings having at least 2 a’s

81. Simplification of CFG: Removing useless symbols, Null (epsilon) –productions and unit productions. Simplification of CFG:, Null (epsilon) –productions

82. Removal of Useless Symbols A symbol can be useless if it does not appear on the right-hand side of the production rule and does not take part in the derivation of any string. That symbol is known as a useless symbol. Similarly, a variable can be useless if it does not take part in the derivation of any string. That variable is known as a useless variable.

83. For Example: T →  aaB  |  abA  |  aaT    A →  aA    B → ab | b   C → ad   In the above example, the variable 'C' will never occur in the derivation of any string, so the production C → ad is useless. So we will eliminate it, and the other productions are written in such a way that variable C can never reach from the starting variable 'T’. Here A is also useless because there no way to terminate it can never produce the terminal. To remove this useless produ ction A →  aA    We will find all variables which will never lead to a terminal as such as variables A then we will remove all the productions in which variable B occurs.

84. We will find all variables which will never lead to a terminal as such as variables A then we will remove all the productions in which variable B occurs. T →  aaB  |  abA  |  aaT    C → ad  is not there in above production so remove it A →  aA   is never produce terminals that is A never be eliminated so remove A. Then the resulting required CFG is T →  aaB  |  aaT   B → ab | b  

85. Problem2 Remove useless symbols S  →  A B   A → a   B  → b C  → a C is not there in above production so remove it S  →  A B   A → a   B  → b  

86. Problem 3 S  →  A B I CA  B →  BC I AB  A → a C →  aB I b Remove B non generating terminals The required CFG is S  → CA  A → a C →  b

87. Removal/Elimination of of Useless Symbols  production. The production S →  is called,  -production. These type of production can only be removed from those grammars that do not generate . Step 1: First find out all nullable, non terminals which deriving  or not. Step 2: For each production A → a construct all productions A,where x is obtained from a by removing 1 or more non terminal from step 1. Step 3; now combine results of step 2 with the original production and remove -production.

88. Example 1 S  → XYX X → OX I  Y→  1Y I  Sol:Given that While removing  - production,we are deleting the rule X →   , Y →   . To preserve the meaning of CFG,we are actually placing  at right hand where ever X & Y appear, S  → X Y X -IF first X at right hand side is  then S  → Y X Similarly, S  → X Y X -IF last X at right hand side is  then S  → X Y -If both X & Y are  then S  → X -If Y=  then S  → X both X are replaced with  then S  → Y Finally S → X Y I YX I XX I X I Y

89. Now let us consider X → OX I  if we replace  at right hand side for x, then X → O Therefore X → OX/0 Similarly Y→ 1Y/1 Finally the CFG, with removal of -Production S → X Y I YX I XX I X I Y X →0 X I 0 Y →1  Y I 1

90. Removing Unit Productions The unit productions are the productions in which one non-terminal gives another non-terminal. Use the following steps to remove unit production: Step 1:  To remove X → Y, add production X → a to the grammar rule whenever Y → a occurs in the grammar. Step 2:  Now delete X → Y from the grammar. Step 3:  Repeat step 1 and step 2 until all unit productions are removed.

91. For example: Remove unit Production S → 0A | 1B | C   A → 0S |  00    B →  1  | A   C →  01    Solution: Given data is that S → C is a unit production. But while removing S → C we have to consider what C gives. So, we can add a rule to S. S → 0A | 1B |  01    Similarly, B → A is also a unit production so we can modify it as B →  1  | 0S |  00    Thus finally we can write CFG without unit production as S → 0A | 1B |  01    A → 0S |  00    B →  1  | 0S |  00    C →  01   

92. Removing Unit Productions The unit productions are the productions in which one non-terminal gives another non-terminal. Use the following steps to remove unit production: Step 1:  To remove X → Y, add production X → a to the grammar rule whenever Y → a occurs in the grammar. Step 2:  Now delete X → Y from the grammar. Step 3:  Repeat step 1 and step 2 until all unit productions are removed.

93. Normal forms of Context free Grammer(CFG) There are two types CFG- Chomsky's Normal Form Definition: CFG is called CNF if all the production rules satifies the one of the following conditions. GNF- Greibach Normal Form CFG- Chomsky's Normal Form CNF stands for Chomsky normal form. A CFG(context free grammar) is in CNF(Chomsky normal form) if all production rules satisfy one of the following conditions: Start symbol generating ε. For example, A → ε. A non-terminal generating two non-terminals. For example, S → AB. A non-terminal generating a terminal. For example, S → a.

94. Steps for converting CFG into CNF (CFG- Chomsky's Normal Form) Step 1:Eliminate start symbol from the RHS if the start symbol T is at the right hand side of any production, creat a production as S Where is the new start symbol. Step 2: In the grammar ,remove the null unit and useless productions. Step3:Eliminate terminals from the right hand side of the production if they exist with other non terminal of terminals. Ex: aA can be decomposed as S RA Here R a etc.. Step4: Eliminate RHS with more than two non terminals. Ex: ABS can be decomposed as RS AB ABS RS  

95. Convert the given CFG to CNF Consider the given grammar as a/a A/B A aBB/  B Aa/b Sol: Given that by the definition of CNF Start symbol generating ε. For example, A → ε. A non-terminal generating two non-terminals. For example, S → AB. A non-terminal generating a terminal. For example, S → a. Step1: → → S new production S → a/ aA / B A → aBB/  B → Aa/b  

96. Step2: Start Symbol only contains  But here A → ε try to remove  → S S → a/ aA /B A → aBB/  B → Aa/b/a To eliminate unit production , Replace B with B production rule. → a/ aA /B S → a/ aA /B A→ aBB → a/ aA /Aa/b B → Aa/b/a  

97. Step3: → aA /Aa A → aBB B → Aa That implies X → a → a/XA/AX/b S → a/XA/AX/b A → XBB B→ AX/b/a X → a  

98. That implies X → a → a/XA/AX/b S → a/XA/AX/b A → XBB B→ AX/b/a X → a → a/XA/AX/b S → a/XA/AX/b A → RB R → XB B→ AX/b/a X → a This is the required CNF for the given CFG.  

99. Greibach Normal Form (GNF) GNF stands for Greibach normal form. A CFG(context free grammar) is in GNF( Greibach normal form) if all the production rules satisfy one of the following conditions: A start symbol generating ε. For example, S → ε. A non-terminal generating a terminal. For example, A → a. A non-terminal generating a terminal which is followed by any number of non-terminals. For example, S → aASB . For example: G1 = {S →  aAB  |  aB , A →  aA | a, B →  bB  | b}   G2 = {S →  aAB  |  aB , A →  aA  |  ε,  B →  bB  |  ε}  

100. The production rules of Grammar G1 satisfy the rules specified for GNF, so the grammar G1 is in GNF. However, the production rule of Grammar G2 does not satisfy the rules specified for GNF as A → ε and B → ε contains ε( only start symbol can generate ε). So the grammar G2 is not in GNF. Steps for converting CFG into GNF Step 1:  Convert the grammar into CNF. If the given grammar is not in CNF, convert it into CNF. You can refer the following topic to convert the CFG into CNF: Chomsky normal form Step 2:  If the grammar exists left recursion, eliminate it. If the context free grammar contains left recursion, eliminate it. You can refer the following topic to eliminate left recursion: Left Recursion Step 3:  In the grammar, convert the given production rule into GNF form. If any production rule in the grammar is not in GNF form, convert it.

101. Example: S → XB | AA   A → a | SA   B → b   X → a   Solution: As the given grammar G is already in CNF and there is no left recursion, so we can skip step 1 and step 2 and directly go to step 3. The production rule A → SA is not in GNF, so we substitute S → XB | AA in the production rule A → SA as: S → XB | AA   A → a | XBA | AAA   B → b   X → a  

102. The production rule S → XB and B → XBA is not in GNF, so we substitute X → a in the production rule S → XB and B → XBA as: S →  aB  | AA   A → a |  aBA  | AAA   B → b   X → a   Now we will remove left recursion (A → AAA), we get: S →  aB  | AA   A →  aC  |  aBAC    C → AAC |  ε   B → b   X → a  

103. Now we will remove null production C → ε, we get: S →  aB  | AA   A →  aC  |  aBAC  | a |  aBA    C → AAC |  AA   B → b   X → a   The production rule S → AA is not in GNF, so we substitute A → aC | aBAC | a | aBA in production rule S → AA as: S →  aB  |  aCA  |  aBACA  |  aA  |  aBAA    A →  aC  |  aBAC  | a |  aBA    C → AAC   C →  aCA  |  aBACA  |  aA  |  aBAA    B → b   X → a  

104. The production rule C → AAC is not in GNF, so we substitute A → aC | aBAC | a | aBA in production rule C → AAC as: S →  aB  |  aCA  |  aBACA  |  aA  |  aBAA    A →  aC  |  aBAC  | a |  aBA    C →   aCAC  |  aBACAC  |  aAC  |  aBAAC    C →  aCA  |  aBACA  |  aA  |  aBAA    B → b   X → a   Hence, this is the GNF form for the grammar G.

105. Prob 1:Remove the useless symbols from given production S→ AB | CA  B → BC| BA  A  → a   C → a B| a  Sol: Given data is that S→ AB | CA  B → BC| BA  A  → a   C → a B| a Step 1:Find the variables which are deriving Terminals.

106. Step 2:Find the variables which are deriving from starting symbols . = Step 3:The union of & U = B is useless symbol reduced grammar G’=(V’,T’,S,P’) V’={A,C} T’={a} S={s}  

107. After removing useless symbols The required productions will be S→  CA  A  → a   C → a

108. Removal of Useless Symbols A symbol can be useless if it does not appear on the right-hand side of the production rule and does not take part in the derivation of any string. That symbol is known as a useless symbol. Similarly, a variable can be useless if it does not take part in the derivation of any string. That variable is known as a useless variable.

109. Proving that some languages are not context free -Pumping lemma for CFLs Lemma Pumping lemma for CFG : If  L  is a context-free language, there is a pumping length  n  such that any string  w ∈ L  of length  ≥ n  can be written as  w = uvxyz , where  vy ≠ ε ,  | vxy | ≤ n , and for all  i ≥ 0, uv i xy i z ∈ L . That is three conditions must satisfy | vxy | ≤ n vy ≠ ε for all  i ≥ 0, uv i xy i z ∈ L Note: Select i such that the resulting string is not in L.

110. Procedure: We are proving in contradiction way. Step1. Assume that L is a context free Step2. The pumping length say n. step3. All strings longer than n can be pumped IwI ≥ n Step4.Now find a string w in L such that IwI ≥ n Step5.Divide W into uvxyz . Step 6. Show that uv i wxy i for some i Step7.then consider the ways that w can be divided into uvwxy . Step8.show that none of these can satisfy all the three pumping lemma conditions at the same time. Step9. w cannot be pumped (contradiction)

111. Prob1. Show that is not CFL.   Sol :Given data is that We have to prove the given language is NOT CFL Note: The grammar has four tuples: CFG=CFL=(V,T,P,S). V - It is the collection of variables or nonterminal symbols( CAPITAL ALPHABETS ). T - It is a set of terminals( small alphabets ). P - It is the production rules that consist of both terminals and nonterminal. S - It is the Starting symbol. Let P= Assume that the given Language is Context free language/Grammer.  

112. According to Pumping Lemma There is a pumping length ‘n’ such that any string w ∈ L of length ≥1 can be written as |w|≥n We can break w into 5 things W= uvwxy such that IvwxI ≤ n vy ≠ ε For all i ≥ 0, uv i wxy i ∈ L Let L is an CFG “n” be the constant length Z= IZI n Split z= uvwxy such that z= u vwx y Here u= vwx = vx = &&& y=  

113. u = uv wx x y(Rewriting without loss of generality) = uvwx y = = Pick i =0 u = (since m and n are NOT SAME) This is contradiction Hence the given Language L is not a CFL. Prob2. Show that is not CFL by using Pumping lemma.  

114. Closure Properties of Context Free Languages Context Free Languages (CFLs) are accepted by  pushdown automata . Context free languages can be generated by context free grammars, which have productions (substitution rules) of the form :  A -> ? (where A ? N and ? ? (T ? N)* and N is a non-terminal and T is a terminal)  Properties of Context Free Languages   Union :  If L1 and L2 are two context free languages, their union L1 U L2 will also be context free. E xample,  L1 = { a n b n c m  | m >= 0 and n >= 0 } and L2 = { a n b m c m  | n >= 0 and m >= 0 }  L3 = L1 U L2 = { a n b n c m  ? a n b m c m  | n >= 0, m >= 0 } is also context free.  L1 says number of a’s should be equal to number of b’s and L2 says number of b’s should be equal to number of c’s. Their union says either of two conditions to be true. So it is also context free language.  Note:  So CFL are closed under Union. 

115. Concatenation :  If L1 and If L2 are two context free languages, their concatenation L1.L2 will also be context free. For example,  L1 = { a n b n  | n >= 0 } and L2 = { c m d m  | m >= 0 }  L3 = L1.L2 = { a n b n c m d m  | m >= 0 and n >= 0} is also context free.  L1 says number of a’s should be equal to number of b’s and L2 says number of c’s should be equal to number of d’s. Their concatenation says first number of a’s should be equal to number of b’s, then number of c’s should be equal to number of d’s. So, we can create a PDA which will first push for a’s, pop for b’s, push for c’s then pop for d’s. So it can be accepted by pushdown automata, hence context free.  Note:  So CFL are closed under Concatenation. 

116. Kleene Closure :  If L1 is context free, its Kleene closure L1* will also be context free. For example,  L1 = { a n b n  | n >= 0 }  L1* = { a n b n  | n >= 0 }* is also context free.  Note : So CFL are closed under Kleen Closure.  Intersection and complementation :  If L1 and If L2 are two context free languages, their intersection L1 L2 need not be context free.  example,  L1 = { a n b n c m  | n >= 0 and m >= 0 } and L2 = ( a m b n c n  | n >= 0 and m >= 0 }  L3 = L1 L2 = { a n b n c n  | n >= 0 } need not be context free.  L1 says number of a’s should be equal to number of b’s and L2 says number of b’s should be equal to number of c’s. Their intersection says both conditions need to be true, but push down automata can compare only two. So it cannot be accepted by pushdown automata, hence not context free.  Similarly, complementation of context free language L1 which is ?* – L1, need not be context free.  Note :  So CFL are not closed under Intersection and Complementation.   

117. Unit-4 Push Down Automata(PDA) Formal definition of PDA: M=( Q, ∑, Γ, q0, Z, F, δ) The PDA can be defined as a collection of 7 components: Q:  the finite set of states ∑:  the input set Γ:  a stack symbol which can be pushed and popped from the stack q0:  the initial state Z:  a start symbol which is in Γ. F:  a set of final states δ:  mapping function which is used for moving from current state to next state. δ: QX(QU ε )U Γ (Γ is pronounced as TOW) It is an Automata machine It recognizes context free languages

118. Major 3 parts Input tape/symbols Finite control Stack Note: stack is string of symbols for some alphabets. TWO TASKS: 1.PUSH (insert) 2. POP(Deletion) Stack: Adding elements is called Stack can represented by TOP Top most element in stack is called TOP TOP is nothing but deletion Push is nothing but adding.

119. Push Down AUTOMATA is more power full than Finite state Automata It means Push down Automata having more memory where as finite state automata having less memory. INPUT FINITE CONTROL ACCEPT Or Reject STACK

120. Basic example check the string accepting. String=000111

121. Example 2:Check the string acceptance. For That is number of 1s are double than 0s 011/001111/000111111…etc..  

122. CFG to PDA Conversion The first symbol on R.H.S. production must be a terminal symbol. The following steps are used to obtain PDA from CFG is: Step 1:  Convert the given productions of CFG into GNF. Step 2:  The PDA will only have one state {q}. Step 3:  The initial symbol of CFG will be the initial symbol in the PDA. Step 4:  For non-terminal symbol, add the following rule: δ(q, ε, A) = (q, α)   Where the production rule is A → α Step 5:  For each terminal symbols, add the following rule: δ(q, a, a) = (q, ε)  for  every terminal symbol  

123. PDA to Context free grammar: Conversion from CFG to PDA Example: We will discus with one example. The given production is S →  aSa S →  bSb S → c Here a,b,c are Terminals &&& S is NON terminal Design the PDA (that is Push && POP) to accept the string. CFG to PDA: Initially we write the Production rules and then POP. That is we need to list the Production and then POP etc.. Now, INPUT SYMBOL S( , ) TOP OF THE STACK = ( ) Here first is I/P symbol The second is TOP of the STACK.     

124. S( , S )=( , a s a)---------2 ----------------3   Now, -------------7  

125.   S.no State Unread Input Stack Transition 1 abbcbba 1 2 abbcbba s 1 3 a bbcbba( poping a a sa 2 4 bbcbba sa 5 5 b bcbba b sba 3 6 bcbba sba 6 7 b cbba b sbba 3 S.no State Unread Input Stack Transition 1 abbcbba 1 2 abbcbba s 1 3 a bbcbba( poping a a sa 2 4 bbcbba sa 5 5 b bcbba b sba 3 6 bcbba sba 6 7 b cbba b sbba 3 8 cbba sbba 6 9 c bba c bba 4 10 b ba b ba 7 11 ba ba 6 12 5 8 cbba sbba 6 9 c bba c bba 4 10 b ba b ba 7 11 ba ba 6 12 5

126. UNIT-5 Turing Machine Introduction A Turing Machine is an accepting device which accepts the languages (recursively enumerable set) generated by type 0 grammars. It was invented in 1936 by Alan Turing. Definition A Turing Machine (TM) is a mathematical model which consists of an infinite length tape divided into cells on which input is given. It consists of a head which reads the input tape. A state register stores the state of the Turing machine. After reading an input symbol, it is replaced with another symbol, its internal state is changed, and it moves from one cell to the right or left. If the TM reaches the final state, the input string is accepted, otherwise rejected. A TM can be formally described as a 7-tuple (Q, X, ∑, δ, q , B, F) where −

127. Q  is a finite set of states X  is the tape alphabet ∑  is the input alphabet δ  is a transition function; δ : Q × X → Q × X × { Left_shift , Right_shift }. q  is the initial state B  is the blank symbol F  is the set of final states Comparison with the previous automaton The following table shows a comparison of how a Turing machine differs from Finite Automaton and Pushdown Automaton.

128. Stack Data Structure Deterministic? Finite Automaton N.A Yes Pushdown Automaton Last In First Out(LIFO) No Turing Machine Infinite tape Yes

129. Example of Turing machine Turing machine M = (Q, X, ∑, δ, q , B, F) with Q = {q , q 1 , q 2 , q f } X = {a, b} ∑ = {1} q  = {q } B = blank symbol F = { q f  } δ is given by − Tape alphabet symbol Present State ‘q ’ Present State ‘q 1 ’ Present State ‘q 2 ’ a 1Rq 1 1Lq 1Lq f b 1Lq 2 1Rq 1 1Rq f

130. Time and Space Complexity of a Turing Machine For a Turing machine, the time complexity refers to the measure of the number of times the tape moves when the machine is initialized for some input symbols and the space complexity is the number of cells of the tape written. Time complexity all reasonable functions − T(n) = O(n log n) TM's space complexity − S(n) = O(n) Here the transition 1Rq 1  implies that the write symbol is 1, the tape moves right, and the next state is q 1 . Similarly, the transition 1Lq 2  implies that the write symbol is 1, the tape moves left, and the next state is q 2 .

131. Note: It is f inite automation In this we can perform read, write and Erase symbols Here we are using a TAPE Tape is divided into squares and each square contains a symbol By using Turing machine only read one symbol at a TIME. a a b b b a a a blank Blank Tape

132. Read(Left Side, Right side)/Write(Adding) A TM can be formally described as a 7-tuple (Q, X, ∑, δ, q , B, F) Turing machine M = (Q, X, ∑, δ, q , B, F) with Q = {q , q 1 , q 2 , q f } X = {a, b} ∑ = {1} q  = {q } B = blank symbol F = { q f  } δ –Transition function Representing: It is represented by state diagram Here we are taking different state cells connected with arrows Arrows-Instructions

133. Example : Design a Turing Machine which recognizes the language L=01*0 (That is starting and ending with zero). Here 1*=1111111111….. L=010,0110,01110,011110… etc Now we take a tape for L=0110 x y y x Blank Blank Blank Blank Blank

134. Example 2 : Design a Turing Machine which recognizes the language L= (n>0) (That is number of 0s=number of 1s). Here L=01,0011,000111,00001111… etc Now we take a tape for L=000111 Note: Algorithm for design C hange 0 to x Move right to first 1 if none reject Change 1 to y Move left to left most 0 Repeat the above steps until no more 0 Make sure no more 1s remains..  

135. 1 1 1 blank blank etc Change to x Move right to first 1 if none reject No more 1s.

136. Problem-1: Draw a Turing machine to find 1’s complement of a binary number.  1’s complement  of a binary number is another binary number obtained by toggling all bits in it, i.e., transforming the 0 bit to 1 and the 1 bit to 0.   Approach:  Scanning input string from left to right Converting 1’s into 0’s Converting 0’s into 1’s Move the head to the start when BLANK is reached.

137. Steps:  Step-1.  Convert all 0’s into 1’s and all 1’s into 0’s and go right if B is found go to left.  Step-2.  Then ignore 0’s and 1’s and go left & if B found go to right Step-3. Stop the machine. Here,  q0  shows the initial state and  q1  shows the transition state and  q2  shows the final state.  And 0, 1 are the variables used and R, L shows right and left.  Explanation:  State q0 replace ‘1’ with ‘0’ and ‘0’ with ‘1’ and move to right. When BLANK is reached move towards left. Using state ‘q2’ we reach start of the string. When BLANK is reached move towards right and reaches the final state q2. 

138. The Post Correspondence Problem (PCP), I ntroduced by Emil Post in 1946, is an undecidable decision problem. The PCP problem over an alphabet ∑ is stated as follows − Given the following two lists,  M  and  N  of non-empty strings over ∑ − M = (x 1 , x 2 , x 3 ,………, x n ) N = (y 1 , y 2 , y 3 ,………, y n ) We can say that there is a Post Correspondence Solution, if for some i 1 ,i 2 ,………… i k , where 1 ≤ i j  ≤ n, the condition x i1  ……. x ik  = y i1  ……. y ik  satisfies. Example 1 Find whether the lists M = (abb, aa, aaa ) and N = ( bba , aaa , aa) have a Post Correspondence Solution?

139. List A List B i 1 abb bba 2 aa aaa 3 aaa aa Here, x 2 x 1 x 3  = ‘ aaabbaaa ’ and  y 2 y 1 y 3  = ‘ aaabbaaa ’ We can see that x 2 x 1 x 3  = y 2 y 1 y 3 Hence, the solution is  i = 2, j = 1, and k = 3.

140. from 2 List A: aa List B:aaa From 1 List A: aaabb List B:aaabba From 3 List A: aaabbaaa List B:aaabbaaa Satisying two sequences Hence the the rquired solution for the given pcp problem is 2,1,3

141. Example 1 Find whether the lists M = (1,10111,10) and N = (111,10,0) have a Post Correspondence Solution? List A List B i 1 1 111 2 10111 10 3 10 List A List B i 1 1 111 2 10111 10 3 10

142. from 2 List A: 10111 List B: 10 From 1 List A: 10111 1 List B: 10 111 From 1 List A: 10111 1 1 List B: 10 111 111 From 3 List A: 10111 1 1 10 List B: 10 111 1110 Mathing hence the the rquired solution for the given pcp problem is 2,1,1,3

143. Example 3 Find whether the lists M = (10,011,101) and N = (101,11,011) have a Post Correspondence Solution? List A List B i 1 10 101 2 011 11 3 101 011 List A List B i 1 10 101 2 011 11 3 101 011 List A: 10 List B: 101 List A: 10 101 List B: 101