Contents

1. Deterministic Finite Automata
2. Non-deterministic Finite Automata
3. RegEx
4. Non-Regular Languages
5. Grammars
6. Context Free Languages
7. Turing Machines

Languages

An alphabet is a non-empty set of symbols, usually denoted \(\Sigma = \{a,b,c,\dots\}\). \(\renewcommand{\epsilon}{\varepsilon}\)

A language is then a (potentially infinte) set of finite strings (words) over an alphabet. The set of all words is denoted \(\Sigma*\).

In CS, we can model every decision problem as a question "is a given string in a given language L?", thus, one can see the usefulness of formal languages.

Contents

1. DFA
2. Regular Languages

DFA

The DFA can either be represented in a state diagram, or in a transition table:

A monoid is a tuple of a set, an associative binary equation, and an identity:

• \((\mathbb{N}_0, +, 0)\) where + is integer addition, and \(\mathbb{N_0} \) are nonnegative integers.
• \((\Sigma*, \circ, \varepsilon)\) where \(\circ\) is string concat, is a monoid.

Note well that the concat symbol \(\circ\) can also be written \(\cdot\) or omitted entirely.

Formally, the way a DFA computes can be defined with the help of the extended transition function: \[\hat{\delta} : Q \times \Sigma* \longrightarrow Q\] Which can be recursively defined (in a haskell like form) over a string \(w = w' \circ a\) as \begin{align} \hat{\delta}(q, \varepsilon) &= q\\ \hat{\delta}(q, w' \circ a) &= \delta(\hat{\delta}(q, w'), a). \end{align}

The accepted language of a DFA \(M = (Q, \Sigma, q_0, F, \delta)\) is \(L(M)\), such that \[L(M) = \{ s \in \Sigma* : \hat{\delta} (q_0, s) \in F \}.\]

The run is an accepting run is a run that ends in an accepting state, thus \(s\) is accepted if its run is accepting - we can also define \(L(M)\) using accepting runs.

Regular Languages

A language L is regular if it is accepted by some DFA.

Trivially, the empty language \(L=\varnothing\) is regular (any DFA with no accept states), and \(\Sigma* \) is regular (define \(\delta(q_0, \_) = q_0\)).

Naturally not all languages are regular, one particular one to note is that the language of (binary) palindromes is not regular.

Since languages are sets of strings, we can naturally perform set operations: \(\overline{L}, L \cap M, L \cup M\). There are also a few string-specific operators, such as

• reverse L: reverse all strings in L
• truncate L n: trim all strings in L to at most \(n\) long
• concat L1 L2: like cross product, but concactenating strings together instead of tuple pairing

For completement: where \(\overline{L} = L \setminus \Sigma* \), this is closed, as one can just invert the accept and reject states of the DFA.

For intersection: given \(L_1, L_2\), \(L_1 \cap L_2\) is regular, this is closed. Given \(M_1 = (Q_1, \Sigma, q_1, F_1, \delta_1)\) and \(M_2 = (Q_2, \Sigma, q_2, F_2, \delta_2)\), we can construct an intersection automaton like the following:

Note that \(L_1\) regular, \(L_2\) regular \(\implies L_1 \cap L_2\) regular is a one-way implication. If we take \(L_1\) to be the set of palindromes, \(L_2\) being all zeroes 0*, their union is clearly regular, but the separate languages are not.

For union, this is also closed. We can similarly construct a union automaton.

Set difference is closed, since \(L_1 \setminus L_2 = L_1 \cap \overline{L_2} \).

Set reverse \(L^{rev}\) is... well it's closed, but it's not so simple with only DFAs. Intuitively, we want to reverse all the arrows, and make all the finish states start states, and vice versa, but of course, more often than not, this'll break a DFA rules, which means we need to introduce another abstraction:

Contents

1. NFAs
2. Transition Functions, \(\varepsilon\)-closure, Runs

NFAs

A non-deterministic finite automata, an NFA, is like a DFA, but you no longer have so much of the restrictions.

An NFA. Note the multiple possible transitions, missing transitions, and epsilon transitions.

Going back to our \(L^{rev}\), we still can't have multiple start states, however, we can merely add a new start state, and add \(\varepsilon\)-transitions to all the would've-been start states.

A DFA has a clear, linear progression, but how does an NFA run? An NFA runs like a multiple world theory, where every time the NFA encounters multiple possible transitions, the NFA "branches" into multiple worlds which each going to one possible transition.

If an NFA world reaches a state with no possible transitions, it crashes, and is considered a reject by default.

As long as at least one world reaches a finish state, the NFA run is considered an accept.

A computer simulating an NFA would basically be doing a brute force DFS/BFS search.

We can think of DFAs as being strict subsets of NFAs, where there can only be one world and other special conditions.

Transition Functions, \(\varepsilon\)-closure, Runs

Let's try to formally define NFAs.

To define the extended transition function however, we need to first of all look at epsilon-closure: ECLOSE().

Thus, the language accepted by an NFA can be defined in two ways, either as the set of all strings whose extended transition functions contain some finish state, \[L(M) = \{s \in \Sigma* : \hat{\delta} (q_0, s) \cup F \neq \varnothing\}\] or the set of all strings which have an accepting run.

Reduction to DFA

Are NFAs more powerful than DFAs? And by that, we mean can NFAs accept languages which DFAs can't?

Well the answer to that is no. NFAs can reduce to DFAs. Similar to how one DFA can simulate two DFAs like in intersection automata, we can do something similar for simulating an NFA.

An NFA's state information can be captured by a set of states, so we can just have a DFA with states corresponding to \(2^Q\) in the NFA, and transitions between them.

Of course, drawing all of these states is not feasible for any significant number of NFA state0s, especially as there would probably be a lot of redundant states, and thus the machine should be built up incrementally. Start from \(\textrm{ECLOSE}(q_0)\) and work from there.

In general, this means that a language is regular
 iff it is accepted by a DFA
 iff it is accepted by an NFA.

Contents

1. Regex
2. Regex to NFA
3. Generalised NFA

Regex

Sure, "regex" on most systems have way more symbols to make life easier, but this is sufficient to generate all regular languages.

In terms of operator precedence, it goes \(*, \cdot, +\).

Some examples then, over \(\Sigma = \{a,b\}\):

• (a+b)*: effectively \(\Sigma* \).
• (a+b)*(a+bb), any word which ends in "a" or "bb".
• (aa)*(bb)*b, any word made up of even "a"s followed by even "b"s, ending in a "b".
• (aa+b)*, all consecutive "a"s must be of an even number.

Often, if a regex can be understood in plain english, one can turn that regex into a DFA or NFA directly via creative thinking, but there is a modular algorithmic way of doing so, since

Regex to NFA

Theorem. A language is accepted by an NFA/DFA \(\iff\) it is generated by a regex.

Proof. We have two algorithms, one to turn a regex to an NFA, and vice-versa.

Regex to NFA

This can be done modularly based on the recursive definition of a regex string. Our base cases (below) can be modelled by three different "modules":

Then we have our recursive / inductive cases: \(R_1 + R_2\), \(R_1 \cdot R_2\), and \(R*\). A rectangle, in this case, represents a whole machine.

As an aside have a think about the language \(\varnothing* \). What does that make? Well, concating \(\varnothing\) with anything is just ... \(\varnothing\), but the definition of kleene star is 0 or more times: i.e. \(\{\varepsilon\} \cup \varnothing \cup \varnothing^2 \cup \dots\), thus \(\varnothing* = \{\varepsilon\}.\)

NFA to Regex

This is better explained going along with an example:

Our goal is to slowly eliminate all the nodes one at a time, reflecting their effect by changing arcs into smaller regex expressions. First though, we need to add a start \(q_s\) and unique final \(q_f\) state and transition to them with epsilon:

Start by eliminating \(q_3\). Possible paths are \(\langle q_2,q_3,q_2 \rangle :10*\) and \(\langle q_2, q_3, q_f\rangle : 1\varepsilon = 1\). Thus, we can have a self loop on \(q_2\) to be \(10*\) and modify \(q_2 \longrightarrow q_f\) to be \(1 + \varepsilon\)* to represent the two possible choices. Then, \(q_3\) becomes redundant and can be removed.

* Technically, the transition \(q_2 \longrightarrow q_f : \varepsilon\) remains unaffected, but since we also have a new transition \(q_2 \longrightarrow q_f : 1\), we simplify the two parallel transitions into one: \(1 + \varepsilon\). This is very important to note.

Eliminate \(q_2\) using a similar process.

Eliminate \(q_1\)

Finally, eliminate \(q_0\)

Then, we simply read off the last remaining transition for our regex.

Now sure, it's not the cleanest, shortest, or most efficient, but it is a regex, and that's all that matters. $$\tag*{$\Box$}$$

Generalised NFA

The run of a GNFA M on a word \(s\) is a sequence of states \(r_0 .. r_n\) such that \(r_0 = q_0\), and \[\exists s_1 .. s_n \in \Sigma* : s = s_1 .. s_n \textrm{ and } \forall i \in [1..n] \; s_i \in L(\delta(r_{i-1}, r_i)).\] Plain english: \(s\) can be broken down into substrings such that there is a transition that matches each substring.

Theorem. Every NFA can be converted to an equivalent GNFA. This is techically what we have done in the NFA to Regex section, but with the \(\varnothing\) lines omitted for simplicity, which they often can be.

With this fact we can now define our elimination process using some very complicated maths language.

Assuming we have already converted our NFA to a GNFA, and we want to eliminate a state \(q_1\), then for all pairs \(q_a, q_b \in (Q \setminus \{q_f, q_1\}) \times (Q \setminus \{q_0, q_1\}\) (pairs which do not include start and finish states): \begin{align} \delta' (q_a, q_b) &= \delta(q_a, q_b) \\ &+ \delta(q_a, q_1) \cdot [\delta(q_1, q_1)*] \cdot \delta(q_1, q_b). \end{align} i.e. The existing a to b, or a to 1, any number of 1s, then 1 to b.

Introduction

1. Myhill-Nerode
2. Pumping Lemma

Let \(L = \{0^n1^n : n \in \mathbb{N}\}\): i.e. equal number of zeroes and ones. Is this regular?

Intuitively, it isn't, since one would need to keep track of both the number of zeroes and ones, and thus would need inifite memory, impossible on a finite state machine. But how do we formally prove this?

We can use closure properties, especially because its quick:

But if we can't, there's two main ways.

Proving Nonregularity: Myhill-Nerode

If \(\hat{\delta}(q_0, \textrm{cat}) = \hat{\delta}(q_0, \textrm{rabbit}) = \hat{\delta}(q_0, \textrm{rat})\), then we can say these three strings are equivalent.

These can be thought of as equivalent relations (remember cs130?), and following on from this, we can partition \(\Sigma* \) into equivalence classes based on what states they end up in.

Definition. The index of a language is its number of equivalence classes. This can be written \(\equiv_L\).

Note: \(x, y\) both do not have to be in L. As long as \(xz \in L\) and \(yz \not \in L\) then this is sufficient.

Since DFAs have finite states, a regular language must have finite equivalence classes.

Thus if a language has infinite equivalence classes, it can't be regular:

Theorem. (Myhill-Nerode) L is a regular language if and only if \(\equiv_L\) is finite.

Proving Nonregularity: Pumping Lemma

Infiniteness or Finiteness

Looking at given a DFA, can we determine whether or not it accepts a language of an infinite length?

Well, it must have a cycle that is (a) reachable from the start and (b) can reach the accept state: cycle => inf words

But if we have infinite words, it must be necessary to have a cycle, since the machine itself is finite: inf words => cycle.

Thus there is an if and only if. We can use this princple to find another way of proving irregularity.

Pumping Lemma

NOTE WELL that this is not an if and only if. , and , but not pumpable strings \(\implies\) L regular.

• L regular \(\implies\) pumpable strings
• Contrapositively unpumpable strings \(\implies\) L irregular
• but pumpable strings \(\mathrel{\rlap{\hskip .75em/}}\implies\) L regular. You cannot use the pumping lemma to prove something is regular.

Use the contrapositive (unpumpable strings \(\implies\) L irregular) to prove irregular languages.

Contents

• Grammars
• Derivation
• Chomsky's Heirarchy
• DFA to Linear Grammars

Grammars

A grammar is a series of rules to form words: <sentence> -> <noun_phrase> <verb phrase> <noun phrase>

Recall Backus-Naur form from A level Comp Sci.

If \(\alpha \implies \beta\) then \(\alpha\) yields \(\beta\) (it might be a single not a double arrow but what do I care -- it's just an arrow.)

If you can have a path of successive yields from the start variable, to a desired string \(w\), this is a derivation of \(w\) from G (the grammar). We write \(S \overset{*}{\implies} w\).

The language of a grammar \(L(G) = \{w \in \Sigma* : s \overset{*}{\implies} w \}\) -- that is, all strings derivable via G.

Derivation

Take \(G = (\{S\}, \{0,1\}, R, S :\) \begin{align} R:= S &\longrightarrow 0S1S &\pod{r_1} \\ S &\longrightarrow 1S0S &\pod{r_2} \\ S &\longrightarrow \epsilon &\pod{r_0} \end{align}

A leftmost derivation means always expanding the leftmost variable. \[S \implies 0S1S \implies 01S0S1S \implies 0010S1S0S1S \implies \cdots \implies 010101.\] A rightmost derivation should thus be obvious.

A parse tree shows the order of derivation in, unsurprisingly, a tree.

A grammar is ambiguous if it can be generated via multiple parse trees (of a single directional derivation).

Ambiguity is generally not desired, however it is a part of the grammar, and not the language itself.

Most grammars can be rewritten to be non-ambiguous, but there are some "inherently ambiguous" grammars.

Chomsky's Heirarchy of Grammars

Yes, That Chomsky, the guy who also wrote stuff like Manufacturing Consent.

Chomsky puts grammars in a heirarchy, with each larger rank containing all the languages of the previous rank.

Given \(G = (V, \Sigma, R, S)\) and \(A, B \in V, x \in \Sigma*, \alpha, \beta, \gamma, w \in (V \cup \Sigma*)\), if

• Type 3. \[ \begin{array}{} A \longrightarrow xB \\ A \longrightarrow x \end{array} \;\;\textrm{ xor }\;\; \begin{array}{} A \longrightarrow Bx \\ A \longrightarrow x \end{array} \] Are the only rule forms permitted, it is a Regular language, with the two forms being called right and left linear grammars respectively.
• Type 2. \[A \longrightarrow w\] where \(w\) is any comibnation of variables and terminals, the language is a context free language
• Type 1. \[\alpha A \gamma \longrightarrow \alpha \beta \gamma\] i.e. we care what's around \(A\), then it is a context sensitive language.
• Type 0. \[\alpha \longrightarrow \beta\] i.e. go nuts, then it is a recursively enumerable language.

In summary, \[\textrm{Regular } \subset \textrm{ Cont. free } \subset \textrm{ Cont. Sens. } \subset \textrm{ Rec. Enumerable} \]

DFA to L/R Linear Grammars

Whilst for a linear grammar \(x\) can be any string, in a strictly linear grammar, \(x\) has to be a single letter. This doesn't make the grammar any less powerful, just simpler to work with.

Right Linear

The general rule is \[ \forall q, q' \in Q, a \in \Sigma,\textrm{ if } \delta(q,a) = q', \textrm{add rule } q \longrightarrow aq' \] \[ \forall q \in F, \textrm{ add rule } q \longrightarrow \epsilon\]

Example. Take the DFA shown with \(M = (Q = \{X,Y,S\}, \Sigma = \{a,b\}, S, F=\{S\}, \delta)\):

This will make a grammar \(G = (V = \{S,X,Y\}, \Sigma, R, S)\) where the variables are just the states, however we now need to figure out what the production rules lead to.

The idea is to find all strings which will take us from the given one to an accept state. But we can start with just rewriting the state transition function: \begin{align} S &\longrightarrow \epsilon | bS | aX \\ X &\longrightarrow bS | aY \\ Y &\longrightarrow aY | bY \end{align} We can then strip away dead states (Y) to get \begin{align} R := S &\longrightarrow \epsilon | bS | aX \\ X &\longrightarrow bS. \end{align} Which is a left linear grammar.

Again, cleaning up dead states is helpful, but not necessary in the exam.

Left Linear

Left linear grammars are slightly more difficult, since we're effectively working backwards from end to beginning. Thus, our accept state is our starting variable.

If there are multiple accept states, we can just \(\epsilon\)-transition all the accept states into one single state (since NFA \(\leq\) DFA, to use reducibility syntax)

The start state \(q_0\) must of course also yield \(\epsilon\).

Example. Take the following DFA

Our grammar will be \(G = (\{A,B,C,D,E\}, \{0,1\}, R, E)\) and \begin{align} R := E &\longrightarrow B1 | A0 \\ D &\longrightarrow E0 | E1 | C1 | D0 | D1 \\ C &\longrightarrow B0 \\ B &\longrightarrow A1 | C0 \\ A &\longrightarrow \epsilon | C0 \end{align} And since D is a dead state, we can clean it up to get \begin{align} R := E &\longrightarrow B1 | A0 \\ C &\longrightarrow B0 \\ B &\longrightarrow A1 \\ A &\longrightarrow \epsilon | C0 \end{align}

Introduction

1. Pushdown Automata
2. CFGs to PDAs
3. PDAs to CFGs
4. Chomsky Normal Form
5. String Testing
6. Pumping Lemma
7. Properties of CFLs

A context free language (CFL) is simply one that is written using a context free grammar.

Some examples of CFLs are \begin{align} L &= \{0^n1^n : n \geq 0\} \\ L &= \{[(+)]*:\textrm{ brackets are balanced}\} \\ L &= \{w\#w^R\} \pod{w^R\textrm{ meaning w is reversed}} \end{align} And we want a way to be able to parse them.

Pushdown Automata

We already have DFA and NFA for regular languages, why not augment them with something? A lot of context free languages can be parsed if you have a LiFo data structure, so why not add a stack?

This makes a push-down automaton.

PDA transitions are annotated \(a,c \longrightarrow b\), meaning read \(a\), pop \(c\), push \(b\):

• Any of \(a,b,c\) can be \(\epsilon\) (i.e. don't pop, don't push, etc.)
• \(\epsilon,\epsilon \longrightarrow \$\) is what denotes the starting transition: "push $ and move".
• \(\epsilon, \$ \longrightarrow \epsilon\) is what denotes the end transition: "pop $ and move".

The reason why we use $ is that, like C and arrays, a PDA doesn't know the length of its stack, so it's helpful to have an indicator (like \0)

Example. The PDA for \(L = \{0^n1^n : n \geq 0 \} \) is

Example. The PDA for \(L = \{w\#w^R\} \pod{w^R\textrm{ meaning w is reversed}}\) is

The language \(L = \{w\#w\}\) is actually much more difficult, and is not solvable with a stack.

Example. The PDA for \(L = \{ww^R\}\) is slightly harder, since there's no indication of when they reverse.

Essentially at any time they could reverse, and we just non-deterministically move to the other state.s

Sometimes, we want to push a whole bunch of things for one input. The transition function can be extended to push a string instead: \[a, c \longrightarrow b_1b_2\cdots b_r\] Which is equivalent to \(a,c \longrightarrow b_1\) followed by \(\epsilon,\epsilon \longrightarrow b_2\), ..., \(\epsilon, \epsilon \longrightarrow b_r\).

Pushdown Automata accept precisely the set of all context-free languages.

CFGs to PDAs

We have a non-deterministic algorithm to compute the leftmost derivation of a string, should it exist.

• Set currentString to \(s\)
• Do:
  • if the leftmost element of currentString is a variable A, then select any grammar rule for A, replace A by the other side of this rule, and record.
  • if the leftmost is a terminal \(a\), then read next input, and check if is the same as \(a\). If so, remove \(a\). Else, reject the branch.
  • if string is now empty, then accept, output recorded rules.

Thus, we have an algorithm to make a string from a grammar.

We can then convert this to a PDA compatible algorithm, namely:

• Push \(s \cdot \$ \) onto the stack (last in first).
• Do:
  • If top is a variable A, then select node for A, pop A and push right hand side.
  • If top is a terminal \(a\), then read the next symbol. If it's the same, pop \(a\).
  • If top is \(\$\), then pop $ and accept.

We can thus make a machine with three states: a start \(q_s\), a loop \(q_2\), and an accept \(q_f\).

i.e. just write all the rules on the middle \(q_2\).

Example. Take \(L = \{0^n 1^n : n \geq 0\}\) which gives \begin{align} R := S &\longrightarrow 0S1 \\ S &\longrightarrow \epsilon \end{align} This makes a PDA which looks like

This is effectively brute forcing, but we can convert the grammar into a specific form which makes this deterministic (which will be covered later.)

PDAs to CFGs

To convert a PDA to a CFG, we want to first transform it into a normalised form:

Thus \(\forall p, q \in Q\), we have a variable \(A_{pq}\) (p can equal q)

And \(A_pq\) generates all strings that can transition from \(p\) to \(q\), with an empty stack at start and end.

Thus the language accepted is generated by \(A_{q_s q_f} \).

1. \(\forall p \in Q\), make a rule \(A_{pp} \longrightarrow \epsilon\).
2. \(\forall p,q,r \in Q\), make rule \(A_{pq} \longrightarrow A_{pr} A{_rq} \)
3. \(\forall p,q,r,s \in Q,\; u \in \Gamma,\; \alpha, \beta \in \Sigma_\epsilon\) (every 4 states, a stack letter \(u\), and letters \(\alpha, \beta\))), if the transition \(\delta(p,\alpha,\epsilon)\) can go to the state \(r\) and pushes \(u\) (contains \((r,u)\)), make a rule \(A_{pq} \longrightarrow \alpha A_{rs} \beta\).

   

Chomsky Normal Form

Chomsky normal form is a normalised form of a CFG, which is helpful for certain algorithms.

Theorem (Sipser). Any CFG can be converted to CNF.

Conversion into CNF

"See violation, change violation":

• Create a new start \(S_0 \longrightarrow S\) (if needed for start restriction) Expand...
  \[ \begin{array}{rl} &S &\longrightarrow ASB \\ &A &\longrightarrow aAS | a | \epsilon \\ &B &\longrightarrow SbS | A | bb \end{array} \implies \begin{array}{rl} &S_0 &\longrightarrow S \\ &S &\longrightarrow ASB \\ &A &\longrightarrow aAS | a | \epsilon \\ &B &\longrightarrow SbS | A | bb \end{array} \]
• Eliminate all \(A \longrightarrow \epsilon : A \neq S_0\), by essentially creating an new rule for every other variable, removing \(A\) (and replacing into \(\epsilon\) if needed): Expand...
  \[ \begin{array}{rl} &S_0 &\longrightarrow S \\ &S &\longrightarrow ASB \\ &A &\longrightarrow aAS | a | \epsilon \\ &B &\longrightarrow SbS | A | bb \end{array} \implies \begin{array}{rl} &S_0 &\longrightarrow S \\ &S &\longrightarrow ASB | SB \\ &A &\longrightarrow aAS | a | aS \\ &B &\longrightarrow SbS | A | bb | \epsilon \end{array} \implies \begin{array}{rl} &S_0 &\longrightarrow S \\ &S &\longrightarrow ASB | SB | AS | S \\ &A &\longrightarrow aAS | a | aS \\ &B &\longrightarrow SbS | A | bb \end{array} \]
  And repeat until all epsilons, including newly introduced ones, are gone (except on \(S_0\)). Do not reintroduce \(\epsilon\) on variables that already had it eliminated.
• Eliminate unit variables \(A \longrightarrow B\). Replace with \(A \longrightarrow w\) for every \(B \longrightarrow w\) production. Delete self references. Expand...
  \[ \begin{array}{rl} &S_0 &\longrightarrow S \\ &S &\longrightarrow ASB | SB | AS | S \\ &A &\longrightarrow aAS | a | aS \\ &B &\longrightarrow SbS | A | bb \end{array} \implies \begin{array}{rl} &S_0 &\longrightarrow S \\ &S &\longrightarrow ASB | SB | AS \\ &A &\longrightarrow aAS | a | aS \\ &B &\longrightarrow SbS | bb | aAS | a | aS \end{array} \implies \begin{array}{rl} &S_0 &\longrightarrow ASB | SB | AS \\ &S &\longrightarrow ASB | SB | AS \\ &A &\longrightarrow aAS | a | aS \\ &B &\longrightarrow SbS | bb | aAS | a | aS \end{array} \]
• Add variables and rules to remove occurences \(A \longrightarrow u\) where \(u\) is either a string longer than 1, or a mixture of terminals and non-terminals. Expand...
  \[ \begin{array}{rl} &S_0 &\longrightarrow ASB | SB | AS \\ &S &\longrightarrow ASB | SB | AS \\ &A &\longrightarrow aAS | a | aS \\ &B &\longrightarrow SbS | bb | aAS | a | aS \end{array} \implies \begin{array}{rl} &S_0 &\longrightarrow AU_1 | SB | AS \\ &S &\longrightarrow AU_1 | SB | AS \\ &A &\longrightarrow aU_2 | a | aS \\ &B &\longrightarrow SU_3 | bb | aU_2 | a | aS \\ &U_1 &\longrightarrow SB \\ &U_2 &\longrightarrow AS \\ &U_3 &\longrightarrow bS \\ \end{array} \implies \begin{array}{rl} &S_0 &\longrightarrow AU_1 | SB | AS \\ &S &\longrightarrow AU_1 | SB | AS \\ &A &\longrightarrow V_1 U_2 | a | V_1 S \\ &B &\longrightarrow SU_3 | V_2 V_2 | V_1 U_2 | a | V_1 S \\ &U_1 &\longrightarrow SB \\ &U_2 &\longrightarrow AS \\ &U_3 &\longrightarrow V_2 S \\ &V_1 &\longrightarrow a \\ &V_2 &\longrightarrow b \end{array} \] (The rule \(A \longrightarrow a\) is allowed.)

In CNF every string of length \(n\) can be derived in exactly \(2n-1\) steps,

Since from 1 start variable, we get to \(n\) variables in \(n-1\) steps, and each variable maps to one terminal, adding \(n\) steps, \(\therefore 2n-1\) steps exactly.

String Testing

The Cocke Younger Kasami (CYK) Algorithm is used to test if a string is generated by a CFG (in CNF).

It is based off dynamic programming: for a string \(y = y_1y_2 \cdots y_n\), column \(j\) are the substrings that start at \(y_j\), and row \(i\) of column \(j\) means a substring starting with \(y_j\) and \(i\) letters long.

Inside the array are stored variables which can generate that substring.

The top left cell (\(6, y_0\), i.e. the entire string) must contain \(S\) for the derivation to be a success.

The way the dynamic programming works is that for a square \(i, j\), it'll search up the columns, and down the diagonal, seeing if there's a production rule that makes this substring with any pair.

For reference, here's an animation of a CYK run from wikipedia.

We can even stop the algorithm early if an entire row yields \(\varnothing\), since if a substring cannot be generated, how can the whole string?

Given a string of length \(l\):

Where \(LHS(P \times Q)\) are all variables \(J \in V :\) there exists a rule \(J \longrightarrow XY : X \in P, Y \in Q\).

With an efficiency of \(O(n^3 r)\) where \(n\) is the length of the string, and \(r\) is the number of grammar rules.

Pumping Lemma

The idea is to look at parse trees. If a derived string is too long, a non terminal R must repeat on the same branch of a parse tree.

Thus we can define a \(w = uvxyz\), where \(x\) is created by the second R and \(v\) and \(y\) are the pre- and suffixes of \(x\) created by the first R:

Similar to the DFA loop, we can remove the second R, or reduplicate and add more Rs, giving us

But what is the pumping number?

• Let \(b\) be the longest RHS generation (the longest single rule on a RHS). \(b\) is generally a "small" number (mathematically speaking), like 10.
• No leaf will have more than \(b\) children; the max degree is \(b\)
• For a tree of height \(h\), the number of leaves is at most \(b^h\)
• If a string is very long, and \(b\) is small, then the height must increase along with string length; longer string -> heigher height.
• If \(h > |V|\) (no. variables) then there must be a repeat of a variable. Thus, we want a parse tree height \(\geq |V| + 1\).

Thus the pumping number \(m = b^{|V| + 1}\).

This is by no means the smallest possible number -- it's an upper bound, which is sufficient.

Using the Pumping Lemma

Properties of CFLs

To test if a CFG generates an empty language, we can:

1. Mark all variables which produce a terminal on the RHS.
2. Mark all variables which produce a combination of terminals and already marked variables on the RHS
3. If S is not marked, then \(L(G) = \varnothing\).

To test if a CFL is finite given its grammar, we

• Check for no reachable "grammar loops" ~ a parse tree with no same-branch repeats.
• i.e. The grammar is finite if and only if it cannot generate strings longer than the pumping length.

CFLS are closed under union, concactenation, and kleene (*) closure

and are not closed under intersection and complement.

Contents

1. Turing Machines
2. Turing Recognisability
3. Recursive Enumerability
4. Universal Turing Machines (Halting Problem)
5. Mapping and Reductions
6. Closure of Turing Languages
7. Assorted Questions

Turing Machines

A turing machine has a tape and a moveable read-write head, with an internal state machine.

The tape is infinite, technically in both directions, but often it is easier for it only to be infinite in one.

A turing machine is deterministic by default.

\(\vdash\) denotes the end / start of the tape to the left (for convenience), and ␣ is the blank "no characters here" symbol.

A state transition is described \(a \longrightarrow b, D\) where \(a\) is the read in, \(b\) is the write out, and \(D\) is the direction, which can be \(L, R\) or \(S\) (stay), which is a shorthand for convenience.

Input strings are generally written to the start of the tape in order.

Since all programming languages are turing complete, and can replicate a turing machine, it is sufficient to use pseudocode or structured english to describe a machine's operation, unless specified to draw the thing down.

Exampe. Take the language \(L = \{ w\#w : w \in \{0,1\}*\} \) (all binary strings, replicated, with a # between).

The machine's operation can be described as

Mark the first symbol \(a \in \Sigma\) Go to the first unmarked symbol \(b\) after # If \(a = b\): mark else: REJECT Return to earlist unmarked symbol. Repeat until all symbols marked, then ACCEPT

And can be represented by the following state diagram (where any missing transitions are implied to go to \(q_{reject}\))

Turing Recognisability

A configuration of a TM is a snapshot of the execution at any point. This includes the current state, tape contents, and reader position, denoted \[x = (u, q, v)\] Where \(q\) is the current state, and \(u \cdot v\) is the contents of the tape. The first symbol of \(v\) is where the reader is.

A configuration yields another if it can be reached in 1 step.

• The start configuration is \((\vdash, q_0, w)\) for an input string \(w\)
• The accepting configuration is \(u, q_{accept}, v\) for some \(u,v\)
• The rejecting configuration is \(u, q_{reject}, v\) for some \(u,v\)

The TM halts as soon as ACCEPT or REJECT is encountered.

The run of a turing machine on \(w\) is thus a series of configrations ([c_1 c_2 \cdots c_n\) where \(c_1\) is the start config, and \(c_i\) yields \(c_{i+1} \). it is accepting if \(c_n\) is an accepting configuration.

A TM run has three outcomes:

• Accept
• Reject
• Never halts

The language \(L(M)\) is thus all words where \(M\) has an accepting run.

A language L is turing recongnisable if L is accepted by some machine M.

Note. For \(w \not \in L\), a TM can either reject or never halt.

This set of languages is also called recursively enumerable, and is Type 0 on Chomsky's heirarchy.

Decider/Total Turing Machines are TMs that always halt with either accept or reject.

For a turing machine M, \(L(M)\) is said to be decided by M. These languages are turing decidable. \[\textrm{turing decidable } \subset \textrm{ turing recognisable}. \]

A turing machine is no more powerful if you have more reader heads, more tapes, etc. It is thus allowed to design a TM with a more complex tape structure if easier.

Recursive Enumerability

An Enumeration machine (EM) is a Turing machine with a printer, or output tape.

The enumerator has no input. When the EM enters an enumeration state, all symbols on the internal tape get printed out: "enumerated".

Thus \(L(M)\) is enumerable by an EM, thus "recursively enumerable".

Claim. Enumerable machines are turing machines.

Universal Turing Machines (Halting Problem)

The halting problem is defined as \[HP = \{\langle M, x \rangle : M \textrm{ halts on }x\}\]

The membership problem is defined as \[MP = \{\langle M, x \rangle : x \in L(M)\}\]

The halting problem is turing recognisable: just simulate M on \(x\), and accept when it does.

The crucial point however is: Is the halting problem decidable?

well, no

Theorem. The Halting Problem is indecidable.

Theorem. Membership (MP) is not decidable.

Mappings and Reductions

Since \(HP \leq_m MP\), and HP is undecidable, we have another way to prove that MP is undecidable.

Other problems, like

• \(\epsilon\)-acceptance: \(|{\langle M \rangle : \epsilon \in L(M)\}|}\)
• \(\exists\)-acceptance: \(\{\langle M \rangle : L(M) \neq \varnothing\}\)
• \(\forall\)-acceptance: \(\{ \langle M \rangle : L(M) = \Sigma * \} \)

However, these problems are defined by default over turing machines. It is comparatively extremely easy to verify that a DFA is \(\epsilon\)-accept, or \(\exists\)-accept, etc.

Theorem. A language L is decidable if and only if both \(L\) and \(\overline{L} \) are turing recognisable.

Closure of Turing Languages

Complement. Is a turing recognisable (TR) language closed under complementation?

No. We know that HP is T.R. but not decidable. If \(\overline{HP}\) is decidable, then HP is decidable (because of our theorem) -- contradiction.

Complement is closed for decidable languages, however.

Union. Yes! See the machine:

Intersection. Also yes:

Kleene Star. \(L* \) Yes.

• On input \(w\)
• Go over every partition of \(w\) into substrings
• For each substring run L
• If \(\exists\) a partition : all substrings are accepted, then ACCEPT.

We can also produce different languages by tring to combine different "types" of languages:

In essense, the "strongest" langauge wins, except for the case of two CFLs, whch make a decidable language.

The complement of TR languages are called co-turing recognisable, and can be represented with this diagram:

Assorted Questions

These questions' answers will be collapsed as per usual, which allows one to have a go first (if they can be bothered).

Q1. Is there a decider D, when given a TM M, that decides whether

1. The TM has over 481 states?
2. The TM takes \(\geq 481\) steps on the input \(\epsilon\)?
3. The TM takes \(\geq 481\) steps for some input?
4. The TM takes \(\geq 481\) steps for all inputs?
5. The read head moves more than 481 cells from \(\vdash\) on \(\epsilon\)?
6. Accepts \(\epsilon\)?
7. Accepts any string?
8. Accept every string?

Q2. \(A \leq_m B\) and B is a CFL, is A a CFL?

Q3. If \(A \leq_m B\) and B is regular, is A?

Q4. Are Turing Recognisable languages closed under set difference>?

Q5. Is there a decider D, that given a DFA M with a binary alphabet, decides whether M accepts a string with more zeroes than ones?

Q6. Is there a decider D for the problem, given a regex \(r\), is there another regex \(p\) that \begin{array}{} |p| < |r|, &L(r) = L(p) \end{array}

Q7. Is \(L_c = \{\langle M \rangle : M \textrm{ is a TM, } L(M) \textrm{ is countable}\}\) decidable?

Q8. Is \(L_h - \{\langle M, x \rangle : M \textrm{ is a } DFA,\; M \textrm{ halts on }x\) decidable?