Deterministic Finite Automata

Non-deterministic Finite Automata

• \(\epsilon\) transition
  

  This has an \(\epsilon\) slip that allows the state to transition without reading any input symbol.

  Proof that \(\epsilon\) transition NFA's have an equivalent NFA with just one start state and no \(\epsilon\) transitions.

  Defn: \(\epsilon\) closure: The set of all states that a state can reach on an \(\epsilon\) transition.

  Define a new transition function such that the states attained by the state with \(\epsilon\) transitions further take one symbol.

  For an \(\epsilon\) NFA to be converted to a regular NFA, we define

  \[ \Delta'\left(q,\sigma\right) = \bigcup_{q'\in \epsilon(q)} \] \[ \Delta\left(q', \sigma\right) \]

  where \(\epsilon(q)\) is the \(\epsilon\) closure of q.

  The final states

  \[ F' = \{q | \epsilon(q)\cap F \neq \phi\} \]

  Everything else remains the same.

Combining patterns

DFAs to Regex

Limits of DFAs

Pumping Lemma for regular languages

An alternate way to prove that a language is not regular.

Distinguishability

Myhill-Nerode Relations

Minimizing DFAs and Isomorphism

Context free languages

• Ambiguous CFGs
  

  These are those for which there are more than one parse trees. It is ambiguous if it has more than one leftmost derivation. Use multiple rules to resolve amiguousness.

  However some languages are inherently ambiguous.

  \(a^ib^jc^kd^l | i = j \land k = l \lor i = l \land j = k\)

  basically no possible grammar can make it unambiguous.

• Closure properties
  

  Closed under union, concatenation, kleene closure.

  NOT CLOSED under intersection and complementation.

• Chomsky Normal form
  

  A CFG G is in CNF if every production is of the form \(A\rightarrow BC\) or \(A\rightarrow \sigma\)

  CNF grammars do not generate \(\epsilon\)

  • Remove \(A\rightarrow \epsilon\)
    • For every production \(B\rightarrow \alpha A\beta\), add \(B\rightarrow \alpha\beta\)
  • Remove \(A\rightarrow B\)
    • \(B\rightarrow \beta\) with \(A\rightarrow \beta\)

  First remove all the \(\epsilon\) productions as they give more unit productions.

  Then remove all unit productions.

  This gives the minimum size grammar in CNF.

• Pumping Lemma
  

  This is based on the fact that (almost) all languages are convertible to CNF. If we have a path from the root node \(S\) to a leaf node in the parse tree that is greater than \(n +1\), i.e., \(|w| > 2^{n+1}\) where \(w\) is the length of the string and \(n\) is the number of non-terminals in the productions.

  By PHP, we can clearly see that a symbol is going to be repeated. So we can repeat the entire length in the path, and the parse tree will still be valid. This is the pumping we do.

  For every CFL \(L, \exists k > 0\) s.t. \(\forall z \in L\) s.t. \(|z| \ge k, \exists u,v,w,x,y\) s.t. \(z = uvwxy\) with \(vx \ne \epsilon\) and \(|vwx| \le k\) s.t. \(\forall i \ge 0 uv^iwx^iy \in L\).

  Contrapositive form:

  If \(\forall k > 0, \exists z \in L; |z| \ge k\) s.t. \(\forall u,z,w,x,y\) with \(vx \ne \epsilon\) and \(|vwx \le k\) s.t. \(z=uvwxy\), \(\exists i\ge 0\) s.t. \(uv^iwx^iy \notin L\) then L is not context—free.

  Prover and Spoiler:

  • Prover picks k > 0
  • Spoiler chooses the string \(z\)
  • Prover chooses a split that he wants
  • Spoiler finds the i for which pumped string is outside the language.
• Parsing Algorithms for CFGs — Cocke Kasami Younger
  

  Assumptions: G is in CNF

  Goal: Given \(w \in \Sigma^*\), check if \(S\xrightarrow{\text{ * }} w\)

  \(w = w_1w_2w_3\dots w_n\)

  \(\exists A, B\) s.t. \(S\rightarrow AB, A \xrightarrow{\text{ * }} w_1w_2 \dots w_i, B \xrightarrow{\text{ * }} w_{i+1} w_{i+2} \dots w_n\) for some \(1 \le i \le n\)

  Try out all possible choices of \(i\) and check if \(A\) and \(B\) match. This is done recursively.

• Push Down Automata (non-deterministic)
  

  Basically and NFA with a stack and a stack alphabet.

  \(M = \left(Q, \Sigma, \Gamma, \delta, s, \perp, F\right)\)

  These are in the order = start state, alphabet of the string, alphabet of the stack (string alphabet + non-terminals), transition function, initial state of the stack, and the final states.

  \(\delta \subseteq \left(Q\times \Sigma\cup \{\epsilon\}\times \Gamma\right) \times \left(Q\times \Gamma^*\right)\)

  If \(\left(q, \sigma, A\right), \left(q', B_1B_2B_3\dots B_k\right) \in \delta\) then we read \(\sigma\) from the string, pop \(A\) from the stack, and push all of \(B_1B_2\dots B_k\)

  If \(\left(q, \epsilon, A\right), \left(q', B_1B_2B_3\dots B_k\right) \in \delta\) Read nothing but do the pushing and the popping.

  Acceptance happens when it reaches a final state on reading the entire string.

  Alternatively, empty stack acceptance happens when the string becomes empty and makes the stack empty as well.

• Converting CFGs to PDAs
  

  \(G = \left(N, \Sigma, P, S\right)\)

  Define \(\Gamma = N\cup\Sigma\cup\{\perp\}\)

  For a production \(A \rightarrow \alpha\), add stack transition \(\epsilon, A \rightarrow \alpha\)

  Add transition \(\epsilon, \perp \rightarrow S\)

  Add transition \(\sigma, \sigma \rightarrow \epsilon\)

  This PDA obviously accepts the CFG using empty staack acceptance as a basis.

• Converting from PDAs to CFGs
  

  TL;DR: Absolute pain in the ass

  If you have a PDA with a single state that accepts using an empty stack:

  If \(\left(\left(q,\sigma, A\right), \left(q, B_1B_2\dots B_k\right)\right) \in\delta\) then add the production \(A\rightarrow\sigma B_1B_2\dots B_k\)

  Nothing pushed on the stack case needs to be handled separately.

  To convert a general PDA with a single final state to a PDA that accepts with the empty stack:

  Let \(M = \left(Q, \Sigma, \Gamma, \delta, s, \perp, \{f\}\right)\)

  We define \(M' = \left({q}, \Sigma, \Gamma', \delta', \{q\}, \left(s, \perp, f\right), \phi\right)\)

  Here \(\Gamma' = Q\times\Gamma\times Q\)

  Over here, both the Q's are guesses for us, and we keep on guessing the entire sequence of things that are happening and put it on the stack. So we have an exponential number of items pushed onto the stack.

  Suppose you are at state \(p\) with \(\sigma\) on the input string and the contents on the top of the stack were \(A\). You transition to \(q\) and the stack is now \(B_1B_2\dots B_k\). For each of those you add a guess to the new PDA stack with surrounding states \(pB_1q_1\) and so on upto \(q_{k-1}B_kq_k\). Here \(q_k\) is equal to \(q\).

Effective Computability

• Turing Machines
  

  \(M = \left(Q, \Sigma, \Gamma, \vdash, \circ, \delta, s, t, r\right)\)

  These are in the order state, string alphabet, tape alphabet, left end of the tape, blank symbol on the tape, transition, accept state and reject state.

  \(\delta: Q\times \Gamma \rightarrow Q\times\Gamma\times\{L,R\}\) where the first parentheses denotes the current state and the current symbol under the tape.

  The right parentheses tells you the next state to go to, and the symbol to be written, and whether to move left or right.

  Constraints:

  • If you are on the left delimiter of the tape you can only move to the right.
  • If you are on the accept/reject states, you are stuck there.

  Configurations of a Turing Machine: \(Q\times \Gamma^* \times \mathbb{N}\). These are, in order, current state, tape content, and the position of the tape head.

  • Initial contents are \(\left(s, \vdash x, 0\right)\)
  • Acceptance happens when \(\left(s,\perp x, 0\right) \xrightarrow{\text{ * }} \left(t, y, m\right)\)
  • Rejection happens when \(\left(s, \perp s, 0\right) \xrightarrow{\text{ * }} \left(r, y, n\right)\)

  An accepted language by a turing machine is called recursively enumerable (re). If it is a total turing machine then it is called recursive.

  A total turing machine is one that eithers accepts a string or rejects a string. There is no string on which it never accepts and never rejects. (Basically loops forever on the tape)

  A Multi tape turing machine, as it sounds, is a Turing Machine with multiple tapes. It is also possible to simulate a multi tape turing machine using a Turing Machine with a single tape.

  Rough outline of how it happens:

  • The number of tapes is \(k\), and the number of states is \(S\), and the size of the alphabet is \(|\Sigma|\).
  • Our new Turing Machine has \(\left|\Sigma\right|^k\) pre filled tape cells.
  • The tape alphabet is also enlarged similarly.
  • The characters are now encoded in the new tape in such a way that it contains all possible combinations of the first tape characters in index 0, second tape characters in index 1, and so on.
  • Finally, in a transition, it sweeps across the entire tape and finds where the character is.
  • Once that happens, the tape head sweeps backwards to update the letters that were updated.

  A Universal Turing Machine has 3 tapes, one for the encoding of the TM it is trying to simulate, one for the tape of TM it is simulating, and one to store the states and positions of said turing machines.

  Theorem: \(\exists\) a universal TM

  Membership Problem: Given a TM \(M\) and \(x\), check if \(M\) accepts \(x\).

  The language of this problem is r.e. (this is a fact).

  Halting Problem: Check if \(M\) halts on \(x\).

  The language of this problem is r.e. (this is a fact).

  Property: If \(L\) is both r.e. and co-r.e., then it is recursive. (co-r.e. means complement is recursive)

  Proof: Simulate both on a single turing machine. Whichever accepts, halt and accept/reject accordingly.

• Enumeration Machines
  

  These have no input, there is no need to halt, one work tape and one output tape, there is a special print state that prints the contents of the output tape, clears it and then exits the state.

  A language is r.e. iff there exists an E.M. for it. This is equivalent to a time sharing simulation of M.

• Undecidability and Diagonalization
  

  Theorem(Turing): HP is not recursive.

  Let \(M_x\) be the Turing Machine that is encoded by the string \(x\). If no such thing exists, then let it be the trivial TM accepting everything.

  This way, we get a list of turing machines. Let us assume that this is the complete list of turing machines.

  Now consider a 2D matrix containing strings \(y\) in the row header and TMs \(M_x\) in the column header. The cell says H if the machine halts on the string and L if it loops forever. If our assumption that the list of turing machines being complete is true, then we can always do this table.

  Suppose there is a universal Turing machine \(K\) that halts and accepts if \(M\) halts on \(x\) and halts and rejects if \(M\) loops on \(x\).

  Consider a universal machine \(N\) that takes input \(x\) and runs \(K\) on \((M_x,x)\). If \(K\) rejects the input then \(N\) accepts it and if \(K\) accepts it then \(N\) goes into a loop.

  If \(N\) halts on \(x \Longleftrightarrow K\) rejects \((M_x,x) \Longleftrightarrow M_x\) loops on \(x\). This implies that \(N\) differs from each row of the table at the diagonal. However the list contained every Turing Machine in existence, so the assumption that the table entries are determinable is wrong.

• Reductions
  

  If a problem \(A\) is solvable by making a subroutine call to another problem \(B\), we say that the problem \(A\) is reducible to another problem \(B\).

  Basically all the following are equivalent:

  • if B is True:
      A is True
    else:
      A is False
    

  • \(A\) is reducible to \(B\)
  • \(A \le_m B\)
  • \(A\) can be solved by a subroutine call to \(B\)

  Many-one reductions can be used to prove that something is not recognizable (or vice-versa). In that case only one subroutine call is allowed and the result has to be passed as-is by the outer machine.

  In case you are generating a description of a machine from the input machine, the function that you use to generate the description must be computable and total.

  Also, if \(A \le_m B\), then \(\bar{A} \le_m \bar{B}\).

  Turing reductions are more lax in their rules, allowing multiple subroutine calls and modifying the output. However, they can only be used to demonstrate recursiveness (or the lack of it).

• Examples of undecidable problems
  

  Given a TM \(M\) and a string \(x\), decide if \(M\) accepts \(x\).

  Proof:

  Create a turing machine \(H\) that takes input \(M,x\) and decides whether \(M\) accepts \(x\).

  Create a machine \(D\) that does the opposite of what \(H\) does when given input \(M,M\)

  \(D\) with the input \(D\) will cause a contradiction.

  Therefore \(H\) cannot exist.

  ---

  Undecidability of the Halting Problem using Reduction from TM acceptance

  Proof:

  If \(H\) tell you that it halts, then we can run the simulation in a universal turing machine and see the acceptance. If \(H\) tells you that it doesn't halt, then you can say no for acceptance. Therefore, if the halting problem is solvable, then the acceptance problem is also solvable. But we know for a fact that acceptance problem isn't solvable.

  ---

  Check if a language of a turing machine is empty being undecidable

  Proof:

  We modify the machine \(M\) and create a machine \(M_1\).

  If \(L(M)\) is empty, then it returns false. If \(L(M)\) is non-empty, then it checks if \(w\) is in the language or not.

  We use the description of \(M_1\) to feed into the checker for \(E_{TM}\) that checks if the language is empty or not. Inverting the output of the checker can give us the output of the checker of Acceptance problem.

  Note that the checker for \(E_{TM}\) need not necessarily run the machine description. It only deduces that based on some heuristics that are not our concern. We do not have to find the machine that does that, only prove it does not exist. For which we assume the contrary.

  ---

  Check if a a language of a turing machine is regular or not being undecidable

  Proof:

  We have a machine \(R_{TM}\) that decides whether a TM description is regular or not.

  We need to create a machine \(A_{TM}\) that decides whether the input \((M,x)\) will be accepted or not.

  We create \(M_1\) from \((M,x)\) and runs \(M\) on \(x\) and gives us "true" if the input to \(M_1\), i.e. \(y\) has the form \(0^n1^n\) else it gives "true" if \(M\) gives "true" on \(x\).

  Carefully observe what this is doing. When \(M\) accepts \(x\), its language is \(\Sigma^*\), otherwise it is \(0^n1^n\). So the regular language decider will give "true" if \(M\) accepts \(x\) and "false" otherwise.

  We feed this description of \(M_1\) to the decider \(R_{TM}\) and use the output as the output of \(A_{TM}\).

  ---

  Proof of two machines having equal languages being undecidable

  Suppose a decider for the above problem exists. It takes \(M_1,M_2\) and gives "true" if they are equal. Run it with \(M, M_1\) where \(M_1\) rejects everything and \(M\) is the input to the decider of the empty language problem will solve the empty language problem.

  ---