Category: automata Theory

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, ∑, δ, q0, B, F) where − 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}. q0 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. Machine Stack Data Structure Deterministic? Finite Automaton N.A Yes Pushdown Automaton Last In First Out(LIFO) No Turing Machine Infinite tape Yes Example of Turing machine Turing machine M = (Q, X, ∑, δ, q0, B, F) with Q = {q0, q1, q2, qf} X = {a, b} ∑ = {1} q0 = {q0} B = blank symbol F = {qf } δ is given by − Tape alphabet symbol Present State ‘q0’ Present State ‘q1’ Present State ‘q2’ a 1Rq1 1Lq0 1Lqf b 1Lq2 1Rq1 1Rqf Here the transition 1Rq1 implies that the write symbol is 1, the tape moves right, and the next state is q1. Similarly, the transition 1Lq2 implies that the write symbol is 1, the tape moves left, and the next state is q2. 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) Learning working make money

Pushdown Automata Introduction Basic Structure of PDA A pushdown automaton is a way to implement a context-free grammar in a similar way we design DFA for a regular grammar. A DFA can remember a finite amount of information, but a PDA can remember an infinite amount of information. Basically a pushdown automaton is − “Finite state machine” + “a stack” A pushdown automaton has three components − an input tape, a control unit, and a stack with infinite size. The stack head scans the top symbol of the stack. A stack does two operations − Push − a new symbol is added at the top. Pop − the top symbol is read and removed. A PDA may or may not read an input symbol, but it has to read the top of the stack in every transition. A PDA can be formally described as a 7-tuple (Q, ∑, S, δ, q0, I, F) − Q is the finite number of states ∑ is input alphabet S is stack symbols δ is the transition function: Q × (∑ ∪ {ε}) × S × Q × S* q0 is the initial state (q0 ∈ Q) I is the initial stack top symbol (I ∈ S) F is a set of accepting states (F ∈ Q) The following diagram shows a transition in a PDA from a state q1 to state q2, labeled as a,b → c − This means at state q1, if we encounter an input string ‘a’ and top symbol of the stack is ‘b’, then we pop ‘b’, push ‘c’ on top of the stack and move to state q2. Terminologies Related to PDA Instantaneous Description The instantaneous description (ID) of a PDA is represented by a triplet (q, w, s) where q is the state w is unconsumed input s is the stack contents Turnstile Notation The “turnstile” notation is used for connecting pairs of ID”s that represent one or many moves of a PDA. The process of transition is denoted by the turnstile symbol “⊢”. Consider a PDA (Q, ∑, S, δ, q0, I, F). A transition can be mathematically represented by the following turnstile notation − (p, aw, Tβ) ⊢ (q, w, αb) This implies that while taking a transition from state p to state q, the input symbol ‘a’ is consumed, and the top of the stack ‘T’ is replaced by a new string ‘α’. Note − If we want zero or more moves of a PDA, we have to use the symbol (⊢*) for it. Learning working make money

CFG Simplification In a CFG, it may happen that all the production rules and symbols are not needed for the derivation of strings. Besides, there may be some null productions and unit productions. Elimination of these productions and symbols is called simplification of CFGs. Simplification essentially comprises of the following steps − Reduction of CFG Removal of Unit Productions Removal of Null Productions Reduction of CFG CFGs are reduced in two phases − Phase 1 − Derivation of an equivalent grammar, G’, from the CFG, G, such that each variable derives some terminal string. Derivation Procedure − Step 1 − Include all symbols, W1, that derive some terminal and initialize i=1. Step 2 − Include all symbols, Wi+1, that derive Wi. Step 3 − Increment i and repeat Step 2, until Wi+1 = Wi. Step 4 − Include all production rules that have Wi in it. Phase 2 − Derivation of an equivalent grammar, G”, from the CFG, G’, such that each symbol appears in a sentential form. Derivation Procedure − Step 1 − Include the start symbol in Y1 and initialize i = 1. Step 2 − Include all symbols, Yi+1, that can be derived from Yi and include all production rules that have been applied. Step 3 − Increment i and repeat Step 2, until Yi+1 = Yi. Problem Find a reduced grammar equivalent to the grammar G, having production rules, P: S → AC | B, A → a, C → c | BC, E → aA | e Solution Phase 1 − T = { a, c, e } W1 = { A, C, E } from rules A → a, C → c and E → aA W2 = { A, C, E } U { S } from rule S → AC W3 = { A, C, E, S } U ∅ Since W2 = W3, we can derive G’ as − G’ = { { A, C, E, S }, { a, c, e }, P, {S}} where P: S → AC, A → a, C → c , E → aA | e Phase 2 − Y1 = { S } Y2 = { S, A, C } from rule S → AC Y3 = { S, A, C, a, c } from rules A → a and C → c Y4 = { S, A, C, a, c } Since Y3 = Y4, we can derive G” as − G” = { { A, C, S }, { a, c }, P, {S}} where P: S → AC, A → a, C → c Removal of Unit Productions Any production rule in the form A → B where A, B ∈ Non-terminal is called unit production.. Removal Procedure − Step 1 − To remove A → B, add production A → x to the grammar rule whenever B → x occurs in the grammar. [x ∈ Terminal, x can be Null] Step 2 − Delete A → B from the grammar. Step 3 − Repeat from step 1 until all unit productions are removed. Problem Remove unit production from the following − S → XY, X → a, Y → Z | b, Z → M, M → N, N → a Solution − There are 3 unit productions in the grammar − Y → Z, Z → M, and M → N At first, we will remove M → N. As N → a, we add M → a, and M → N is removed. The production set becomes S → XY, X → a, Y → Z | b, Z → M, M → a, N → a Now we will remove Z → M. As M → a, we add Z→ a, and Z → M is removed. The production set becomes S → XY, X → a, Y → Z | b, Z → a, M → a, N → a Now we will remove Y → Z. As Z → a, we add Y→ a, and Y → Z is removed. The production set becomes S → XY, X → a, Y → a | b, Z → a, M → a, N → a Now Z, M, and N are unreachable, hence we can remove those. The final CFG is unit production free − S → XY, X → a, Y → a | b Removal of Null Productions In a CFG, a non-terminal symbol ‘A’ is a nullable variable if there is a production A → ε or there is a derivation that starts at A and finally ends up with ε: A → …….… → ε Removal Procedure Step 1 − Find out nullable non-terminal variables which derive ε. Step 2 − For each production A → a, construct all productions A → x where x is obtained from ‘a’ by removing one or multiple non-terminals from Step 1. Step 3 − Combine the original productions with the result of step 2 and remove ε – productions. Problem Remove null production from the following − S → ASA | aB | b, A → B, B → b | ∈ Solution − There are two nullable variables − A and B At first, we will remove B → ε. After removing B → ε, the production set becomes − S→ASA | aB | b | a, A ε B| b | &epsilon, B → b Now we will remove A → ε. After removing A → ε, the production set becomes − S→ASA | aB | b | a | SA | AS | S, A → B| b, B → b This is the final production set without null transition. Learning working make money

Undecidable Languages For an undecidable language, there is no Turing Machine which accepts the language and makes a decision for every input string w (TM can make decision for some input string though). A decision problem P is called “undecidable” if the language L of all yes instances to P is not decidable. Undecidable languages are not recursive languages, but sometimes, they may be recursively enumerable languages. Example The halting problem of Turing machine The mortality problem The mortal matrix problem The Post correspondence problem, etc. Learning working make money

DFA Complement If (Q, ∑, δ, q0, F) be a DFA that accepts a language L, then the complement of the DFA can be obtained by swapping its accepting states with its non-accepting states and vice versa. We will take an example and elaborate this below − This DFA accepts the language L = {a, aa, aaa , …………. } over the alphabet ∑ = {a, b} So, RE = a+. Now we will swap its accepting states with its non-accepting states and vice versa and will get the following − This DFA accepts the language Ľ = {ε, b, ab ,bb,ba, …………… } over the alphabet ∑ = {a, b} Note − If we want to complement an NFA, we have to first convert it to DFA and then have to swap states as in the previous method. Learning working make money

PDA & Context-Free Grammar If a grammar G is context-free, we can build an equivalent nondeterministic PDA which accepts the language that is produced by the context-free grammar G. A parser can be built for the grammar G. Also, if P is a pushdown automaton, an equivalent context-free grammar G can be constructed where L(G) = L(P) In the next two topics, we will discuss how to convert from PDA to CFG and vice versa. Algorithm to find PDA corresponding to a given CFG Input − A CFG, G = (V, T, P, S) Output − Equivalent PDA, P = (Q, ∑, S, δ, q0, I, F) Step 1 − Convert the productions of the CFG into GNF. Step 2 − The PDA will have only one state {q}. Step 3 − The start symbol of CFG will be the start symbol in the PDA. Step 4 − All non-terminals of the CFG will be the stack symbols of the PDA and all the terminals of the CFG will be the input symbols of the PDA. Step 5 − For each production in the form A → aX where a is terminal and A, X are combination of terminal and non-terminals, make a transition δ (q, a, A). Problem Construct a PDA from the following CFG. G = ({S, X}, {a, b}, P, S) where the productions are − S → XS | ε , A → aXb | Ab | ab Solution Let the equivalent PDA, P = ({q}, {a, b}, {a, b, X, S}, δ, q, S) where δ − δ(q, ε , S) = {(q, XS), (q, ε )} δ(q, ε , X) = {(q, aXb), (q, Xb), (q, ab)} δ(q, a, a) = {(q, ε )} δ(q, 1, 1) = {(q, ε )} Algorithm to find CFG corresponding to a given PDA Input − A CFG, G = (V, T, P, S) Output − Equivalent PDA, P = (Q, ∑, S, δ, q0, I, F) such that the non- terminals of the grammar G will be {Xwx | w,x ∈ Q} and the start state will be Aq0,F. Step 1 − For every w, x, y, z ∈ Q, m ∈ S and a, b ∈ ∑, if δ (w, a, ε) contains (y, m) and (z, b, m) contains (x, ε), add the production rule Xwx → a Xyzb in grammar G. Step 2 − For every w, x, y, z ∈ Q, add the production rule Xwx → XwyXyx in grammar G. Step 3 − For w ∈ Q, add the production rule Xww → ε in grammar G. Learning working make money

CFL Closure Property Context-free languages are closed under − Union Concatenation Kleene Star operation Union Let L1 and L2 be two context free languages. Then L1 ∪ L2 is also context free. Example Let L1 = { anbn , n > 0}. Corresponding grammar G1 will have P: S1 → aAb|ab Let L2 = { cmdm , m ≥ 0}. Corresponding grammar G2 will have P: S2 → cBb| ε Union of L1 and L2, L = L1 ∪ L2 = { anbn } ∪ { cmdm } The corresponding grammar G will have the additional production S → S1 | S2 Concatenation If L1 and L2 are context free languages, then L1L2 is also context free. Example Union of the languages L1 and L2, L = L1L2 = { anbncmdm } The corresponding grammar G will have the additional production S → S1 S2 Kleene Star If L is a context free language, then L* is also context free. Example Let L = { anbn , n ≥ 0}. Corresponding grammar G will have P: S → aAb| ε Kleene Star L1 = { anbn }* The corresponding grammar G1 will have additional productions S1 → SS1 | ε Context-free languages are not closed under − Intersection − If L1 and L2 are context free languages, then L1 ∩ L2 is not necessarily context free. Intersection with Regular Language − If L1 is a regular language and L2 is a context free language, then L1 ∩ L2 is a context free language. Complement − If L1 is a context free language, then L1’ may not be context free. Learning working make money

Introduction to Grammars n the literary sense of the term, grammars denote syntactical rules for conversation in natural languages. Linguistics have attempted to define grammars since the inception of natural languages like English, Sanskrit, Mandarin, etc. The theory of formal languages finds its applicability extensively in the fields of Computer Science. Noam Chomsky gave a mathematical model of grammar in 1956 which is effective for writing computer languages. Grammar A grammar G can be formally written as a 4-tuple (N, T, S, P) where − N or VN is a set of variables or non-terminal symbols. T or ∑ is a set of Terminal symbols. S is a special variable called the Start symbol, S ∈ N P is Production rules for Terminals and Non-terminals. A production rule has the form α → β, where α and β are strings on VN ∪ ∑ and least one symbol of α belongs to VN. Example Grammar G1 − ({S, A, B}, {a, b}, S, {S → AB, A → a, B → b}) Here, S, A, and B are Non-terminal symbols; a and b are Terminal symbols S is the Start symbol, S ∈ N Productions, P : S → AB, A → a, B → b Example Grammar G2 − (({S, A}, {a, b}, S,{S → aAb, aA → aaAb, A → ε } ) Here, S and A are Non-terminal symbols. a and b are Terminal symbols. ε is an empty string. S is the Start symbol, S ∈ N Production P : S → aAb, aA → aaAb, A → ε Derivations from a Grammar Strings may be derived from other strings using the productions in a grammar. If a grammar G has a production α → β, we can say that x α y derives x β y in G. This derivation is written as − x α y ⇒G x β y Example Let us consider the grammar − G2 = ({S, A}, {a, b}, S, {S → aAb, aA → aaAb, A → ε } ) Some of the strings that can be derived are − S ⇒ aAb using production S → aAb ⇒ aaAbb using production aA → aAb ⇒ aaaAbbb using production aA → aaAb ⇒ aaabbb using production A → ε Learning working make money

Rice Theorem Rice theorem states that any non-trivial semantic property of a language which is recognized by a Turing machine is undecidable. A property, P, is the language of all Turing machines that satisfy that property. Formal Definition If P is a non-trivial property, and the language holding the property, Lp , is recognized by Turing machine M, then Lp = {<M> | L(M) ∈ P} is undecidable. Description and Properties Property of languages, P, is simply a set of languages. If any language belongs to P (L ∈ P), it is said that L satisfies the property P. A property is called to be trivial if either it is not satisfied by any recursively enumerable languages, or if it is satisfied by all recursively enumerable languages. A non-trivial property is satisfied by some recursively enumerable languages and are not satisfied by others. Formally speaking, in a non-trivial property, where L ∈ P, both the following properties hold: Property 1 − There exists Turing Machines, M1 and M2 that recognize the same language, i.e. either ( <M1>, <M2> ∈ L ) or ( <M1>,<M2> ∉ L ) Property 2 − There exists Turing Machines M1 and M2, where M1 recognizes the language while M2 does not, i.e. <M1> ∈ L and <M2> ∉ L Proof Suppose, a property P is non-trivial and φ ∈ P. Since, P is non-trivial, at least one language satisfies P, i.e., L(M0) ∈ P , ∋ Turing Machine M0. Let, w be an input in a particular instant and N is a Turing Machine which follows − On input x Run M on w If M does not accept (or doesn”t halt), then do not accept x (or do not halt) If M accepts w then run M0 on x. If M0 accepts x, then accept x. A function that maps an instance ATM = {<M,w>| M accepts input w} to a N such that If M accepts w and N accepts the same language as M0, Then L(M) = L(M0) ∈ p If M does not accept w and N accepts φ, Then L(N) = φ ∉ p Since ATM is undecidable and it can be reduced to Lp, Lp is also undecidable. Learning working make money

Pushdown Automata Acceptance There are two different ways to define PDA acceptability. Final State Acceptability In final state acceptability, a PDA accepts a string when, after reading the entire string, the PDA is in a final state. From the starting state, we can make moves that end up in a final state with any stack values. The stack values are irrelevant as long as we end up in a final state. For a PDA (Q, ∑, S, δ, q0, I, F), the language accepted by the set of final states F is − L(PDA) = {w | (q0, w, I) ⊢* (q, ε, x), q ∈ F} for any input stack string x. Empty Stack Acceptability Here a PDA accepts a string when, after reading the entire string, the PDA has emptied its stack. For a PDA (Q, ∑, S, δ, q0, I, F), the language accepted by the empty stack is − L(PDA) = {w | (q0, w, I) ⊢* (q, ε, ε), q ∈ Q} Example Construct a PDA that accepts L = {0n 1n | n ≥ 0} Solution This language accepts L = {ε, 01, 0011, 000111, ……………………….. } Here, in this example, the number of ‘a’ and ‘b’ have to be same. Initially we put a special symbol ‘$’ into the empty stack. Then at state q2, if we encounter input 0 and top is Null, we push 0 into stack. This may iterate. And if we encounter input 1 and top is 0, we pop this 0. Then at state q3, if we encounter input 1 and top is 0, we pop this 0. This may also iterate. And if we encounter input 1 and top is 0, we pop the top element. If the special symbol ‘$’ is encountered at top of the stack, it is popped out and it finally goes to the accepting state q4. Example Construct a PDA that accepts L = { wwR | w = (a+b)* } Solution Initially we put a special symbol ‘$’ into the empty stack. At state q2, the w is being read. In state q3, each 0 or 1 is popped when it matches the input. If any other input is given, the PDA will go to a dead state. When we reach that special symbol ‘$’, we go to the accepting state q4. Learning working make money