Title: Math and science / Theory of Computation
Tags: copyright
On every note of this deck, unless a note says otherwise:
Header: Convert regular expression → NFA state diagram

Title: Finite automata
A finite automaton (plural: automata) is a model of computation. Finite automata and their probabilistic counterpart Markov chains are useful tools when attempting to recognize patterns in data. Their formal definition has a 1-1 correspondence with a type of state diagram.
A finite automaton is a 5-tuple (\( Q, \Sigma, \delta, q_0, F \)), where:
1. \( Q \) is a finite set called the states,
2. \( \Sigma \) is a finite set called the alphabet,
3. \( \delta : Q \times \Sigma \to Q \) is the transition function,
4. \( q_0 \in Q \) is the start sate, and
5. \( F \subseteq Q \) is the set of accept states.
Processing of input
When an automaton receives an input string, it can either accept or reject it. A string is accepted if the automaton is in an accept state once the full input string is processed. Formally this is described as:
String acceptance
Let \( M = (Q, \Sigma, \delta, q_0, F) \) be a finite automaton and let \( w = w_1w_2...w_n \) be a string where each \( w_i \) is a member of the alphabet \( \Sigma \). Then \( M \) accepts \( w \) iff a sequence of states \( r_0, r_1, ..., r_n \) is \( Q \) exists with three conditions:
1. \( r_0 = q_0 \)
2. \( r_{i+1} =  \delta(r_i, w_{i + 1})  \text{ for } i = 0, ..., n - 1\), and
3.  \(r_n \in F \) 
\( w \) is rejected iff it is not accepted.
If \( A \) is the set of all strings that machine \( M \) accepts, we say that \( A \) is the language of machine \( M \) and write \( L(M) = A \). We say that M recognizes A.
State machine representation
A finite automaton has a 1-1 correspondence with a graphical state machine representation.
Source: Introduction to the Theory of Computation, Sipser
p35-36

Title: Alphabets and languages
An alphabet is defined to be any nonempty finite set. The members of an alphabet are the symbols of the alphabet.
A string over an alphabet is a finite sequence of symbols from that alphabet.
A language is a set of strings. A language is prefix-free if no member is a proper prefix of another.
A string is a proper prefix of another if it is a prefix but not equal to the other.
We say that a finite machine \( M \) recognizes language \( A \) if \( A = \{w | M \text{ accepts } w \} \). A language is called a regular language if some finite automaton recognizes it.
Example: Examples of alphabets:
\[\begin{aligned} \\
\Sigma_1 &= \{0, 1\} \\
\Sigma_2 &= \{a, b, c, ...., z\} \\
\Gamma &= \{0, 1, x, y, z\} \text{ (symbol: capital gamma)} \\
\end{aligned} \]
Capital Greek characters are used to denote alphabets and lowercase Latin characters are used to denote symbols.
Source: Introduction to the Theory of Computation, Sipser

Title: Regular language operators
Q: Let \( A \) and \( B \) be languages. We define the regular operations union, concatenation and star as follows:
Union
\( A \cup B = \{x \mid x \in A \lor x \in B\} \)  (i.e. as per standard axiom of union for sets)
Concatenation
\( A \circ B = \{ [...] \mid x \in A \land y \in B \} \)
Star
\( A^\star = \{ [...] \mid k \ge 0 \text{ and each } x_i \in A \} \)
The class of regular languages is [...]!
A: xy; x_1x_2...x_k; closed under these three operations
BackOnlyText: Visual Justification
It is quite easy to grasp how regular languages are closed under the above three operations. To do so, consider the state diagrams representing two nondeterministic finite automata \( N_1 \) and \( N_2 \) which accepts languages \( A_1 \) and \( A_2 \) respectively. We can combine them in different ways to achieve union, concatenation and star operations.
Union, \( A_1 \cup A_2 \)
The set of start states is the union of the start states of \( N_1 \) and \( N_2 \).
Concatenation, \( A_1 \circ A_2 \)
Each accept state of \( N_1 \) has an ε-transition to the start state of \( N_2 \).
Star operator, \( A_1^{\star} \)
Each accept state of \( N_1 \) has an ε-transition to the start state of \( N_1 \).
Source: Introduction to the Theory of Computation, Sipser
p44

Title: Nondeterministic finite automata (NFA)
Nondeterministic finite automata definition
A nondeterministic finite automaton is a 5-tuple \( (Q, \Sigma, \delta, q_0, F) \), where
1. \( Q \) is a finite set called the states,
2. \( \Sigma \) is a finite set called the alphabet,
3. \( \delta : Q \times \Sigma_{\varepsilon} \to 2^Q \) is the transition function,
4. \( q_0 \in Q \) is the start sate, and
5. \( F \subseteq Q \) is the set of accept states.
String acceptance
Let \( M = (Q, \Sigma, \delta, q_0, F) \) be a NFA, let \( w \) be a string over the alphabet \( \Sigma \), and let \( \Sigma_{\varepsilon} = \Sigma \cup \{\varepsilon\} \) (where \( \varepsilon \) represents the empty string).
Then \( M \) accepts \( w \) iff we can write \( w = y_1y_2...y_m \) where \( y_i \in \Sigma_{\varepsilon} \) and there exists a sequence of states in \( Q \), \( r_0, r_1, ..., r_m \), meeting three conditions:
1. \( r_0 = q_0 \)
2. \( r_{i+1} \in \delta(r_i, y_{i+1}) \text{, for } i = 0, ..., m-1 \)
3. \( r_m \in F \)
\( w \) is rejected iff it is not accepted.
Every nondeterministic finite automaton has an equivalent deterministic finite automaton (two machines are equivalent iff they recognize the same language). The proof of this is worth studying.
BackOnlyText: Viewed from the perspective of a state machine, nondeterministic finite automata depart from deterministic finite automata by:
1. allowing multiple transitions out of a state for a single symbol in the alphabet.
2. introducing the automatic transitions, denoted with \( \varepsilon \).
3. their parallel computation and acceptance.
Proof outline of NFA an DFA equivalence
Let \( N = (Q, \Sigma, \delta, q_0, F) \) be the NFA recognizing some language \( A \). Try to construct a DFA \( M = (Q', \Sigma, \delta', q_0', F') \) that is equivalent to \( N \).
Construction
States
\( Q' = 2^Q \)
If a DFA is to keep track of the computation of an NFA, it must keep track of all possible active states of the NFA. If an NFA has \( k \) states, an equivalent DFA needs to have \( 2^k \) states, one state for every subset of the NFA's states.
Note how the elements of \( Q' \) are sets! This must be understood in order to make sense of the transition function.
Transitions
For \( R \in Q' \) and \( a \in \Sigma \), let \( \delta'(R, a) = \{q \in Q \mid q \in \delta(r, a) \text{ for some } r \in R \} \)
The transition function for M maps a subset of states of N to a subset of states of N.
Start state
\( q_0' = {q_0} \). Note that for the DFA, the state is a set.
Accept states
\( F' = \{ R \in Q' \mid R \text{ contains an accept state of N}  \} \)
A tweak of the transition function described above is needed to account for the \( \varepsilon \) transitions.
Source: Introduction to the Theory of Computation, Sipser
p48-55

Title: Regular expressions
Regular expressions can be seen as a parallel to arithmetic expressions.
- \( (5 + 3) \times 4 \) is an expression whose symbols represent numbers (e.g. natural numbers) and as a whole represents another number, 32.
- \( (0 \cup 1)0^\star \) is an expression involving languages (sets of strings) and as a whole represents another language, the set of all strings which start with a 0 or 1 and is followed by any number of 0s.
A regular expression \( R \) is a sequence of symbols that is one of:
1. a symbol \( a \) for some \( a \) in an alphabet \( \Sigma \)
2. \( \varepsilon \)
3. \( \emptyset \)
4. \( (R_1 \cup R_2) \), where \( R_1 \) and \( R_2 \) are regular expressions
5. \( (R_1 \circ R_2) \), where \( R_1 \) and \( R_2 \) are regular expressions
6. \( (R_1^*) \), where \( R_1 \) is a regular expression
A regular expression is said to represent a language according to the rules below. We write \( L(R) \) to mean the language of the regular expression \( R \).
1. From item 1, the regular expression \( a \) represents the language \( \{a\} \).
2. From item 2, the regular expression \( \varepsilon \) represents the language \( \{ \varepsilon \} \).
3. From item 3, the regular expression \( \emptyset \) represents the empty language, \( \{\} \).
4. From item 4 & 5, the regular expression \( ( R_1 \cup R_2) \) and \( (R_1 \circ R_2) \) represent the languages obtained by taking the union and concatenation of the languages represented by \( R_1 \) and \( R_2 \).
5. From item 6, the regular expression \( (R_1^\star) \) represents the star of the language represented by \( R_1 \).
We say that two regular expressions \( R_1 \) and \( R_2 \) are equal if they represent the same language, and we write \( R_1 = R_2 \).
This definition is lacking in how it describes 'represents'. Maybe it is a function. I think it's coverage of equality is just sufficient, as it delegates the well defined formulation of set equality.
\( \varepsilon \) vs \( \emptyset \)
The regular expression \( \varepsilon \) represents the language containing a single string, the empty string, \( \{\varepsilon\} \). The regular expression \( \emptyset \) represents the empty language, \( \{\} \).
Precedence order
Star has highest precedence, followed by concatenation, with union last.
\( R^+ \)Shorthand
\( R^+ \) is used as convenient shorthand for \( RR^* \); thus, \( R^* = R^+ \cup \epsilon \).
Two identities
If \( R \) is any regular expression then:
\[ R \cup \emptyset = R \]
\[ R \circ \varepsilon = R \]
BackOnlyText: [Note: Shouldn't there be an extra rule for creating a regular expression from a set? How \( \Sigma \) allowed in the regular expressions given as an example on this card?]
Example: The regular expressions here represent the languages below.
1. \( 0^*10^* \)
2. \( \Sigma^*1\Sigma^* \)
3. \( \Sigma^*001\Sigma^* \)
4. \( 1^*(01^+)^*\)
5. \( (\Sigma \Sigma)^* \)
6. \( (\Sigma \Sigma \Sigma)^* \)
7. \( 01 \cup 10 = \{01, 10\} \)
8. \( 0\Sigma^*0 \cup 1\Sigma^*1 \cup 0 \cup 1 \)
9. \( (0 \cup \varepsilon)1^* = 01^* \cup 1^* \)
10. \( (0 \cup \varepsilon)(1 \cup \varepsilon) \)
11. \( 1^*\emptyset \)
12. \( \emptyset^* \)
1. \( \{w | w \text{ contains a single 1} \} \)
2. \( \{w | w \text{ has at least one 1} \} \)
3. \( \{w | w \text{ contains the string 001 as a subsequence} \} \)
4. \( \{w | \text{ every 0 in } w \text{ is followed by at least one 1} \} \)
5. \( \{w | w \text{ is a string of even length} \} \)
6. \( \{w | \text{ the length of } w \text{ is a multiple of 3} \} \)
7. \( \{01, 10 \} \)
8. \( \{w | w \text{ starts and ends with the same symbol} \} \)
9. \( 01^* \cup 1^* \)
10. \( \{\varepsilon, 0, 1, 01 \} \)
11. \( \emptyset \)
12. \( \{\varepsilon\} \)
Source: Introduction to the Theory of Computation, Sipser
p64-65

Title: Pumping lemma for regular languages
Q: The pumping lemma is useful for showing that a language cannot be represented by a finite state machine.
Can a language be accepted by an automaton?
There are two cases.
1. If a language contains only finite strings, we can create a finite automaton that handles each case.
2. If a language contains infinite strings, we look to the pumping lemma to answer this question.
The gist of the lemma
The gist of the pumping lemma is: if a finite set of states is able to represent an infinite string, then during the state transitions between start and accept states, there must be a [...] at some point. This property can be used to show, by contradiction, that some languages cannot be represented by finite state automata.
Pumping lemma
If \( A \) is a regular language, then there is a number \( p \) (the pumping length) where if \( s \) is any string in \( A \) of length at least \( p \), then \( s \) may be divided into three pieces, \( s = xyz \), satisfying the following three conditions:
1. for each \( i \ge 0, xy^iz \in A \)
2. \( |y| \ge 0 \)
3. [...]
A: loop; \( |xy| \le p \)
BackOnlyText: Interpreting the 3 criteria
The definition can be interpreted as: we know there is a loop of some unknown length in the automata. There is some length such that all strings equal to or longer than this length must 'use' the loop for acceptance (the number of states in the FSA is an upper bound, but there might be a smaller upper bound). Let \( p \) be one such length. If there is a string of the language that is larger than \( p \) then it must passes through some number of states before the loop, the loop, and some number of states after the loop. The three conditions correspond to the statements:
1. We can break the string into \( xy^iz \), where \( x \) passes through the states before the loop, \( y \) corresponds to the loop and \( z \) passes through the states after the loop.
2. The loop exists, so has a non-zero length (rule out the degenerate case).
3. If the string goes through the loop multiple times, there are multiple ways of splitting it into the \( xy^iz \) pieces, by moving one or more of the loop sections into the \( x \) or \( z \) portions. The 3rd condition says that it's possible to do the division into \( xy^iz \) without placing any of the looped section in the \( x \) portion. This is useful for showing some languages to be non-regular. With this in mind, the length \( p \) is the combined length of the beginning and the kernel of the repeated section.
My guess is that the 3rd criteria could be expanded to cover the case where we don't put any looped sections in the \( z \) portion either.
Example: Intuition is misleading
The following two examples highlight the need for the pumping lemma—our intuition is not reliable.
- Language A = \( \{w \mid w \text{ has an equal number of 0s and 1s} \} \)
- Language B = \( \{w \mid w \text{ has an equal number of 01 and 10 substrings} \} \)
Language A is non-regular, language B is regular.
\( \{0^n1^n \mid n \ge 0\} \)
This is a well known example of a non-regular language, proved so using the pumping lemma. The proof outline goes like so:
- Let \( p \) be the[a?] pumping length that must exist by the lemma.
- Consider the string \( s = 0^p1^p \).
- We try to split \( s \) into \( xy^iz \), but find that we can't because,
- \( y \) must contain a mix of 0s and 1s, otherwise \( |xy| \) and \( |y| \) wouldn't meet criteria 1 and 2, but
- you can't repeat \( y \) if it contains a mix of 0s and 1s, as the language requirement is such that no zeros can follow any 1.
- The contradiction implies that the language cannot be represented by a FSA.
Source: Introduction to the Theory of Computation, Sipser
This video quickly conveys the intuitive idea.

Title: Turing machine
Conceptual description: finite state machine + tape
A Turing machine can be thought of as a finite state machine that controls a reading/writing head that moves along a a tape.
The tape, head and state machine
The tape is a long physical 1-dimensional storage device. It has a head which is an object positioned at one of the storage cells; the head is capable of reading and writing to a cell and capable of moving 1 position forward or back inbetween read/write operations. The tape is infinite in one direction. Typically, the tape is considered to start at a zero position and extend to the right indefinitely. The head moves along the tape reading charcaters from it and writing characters to it. The head's movement (including whether to stop moving) is determined by a state machine.
Reading and writing
Reading produces a character from the tape at the head position. This character becomes the next input to the finite state machine. Writing places a character on the tape at the position of the head. The character written is chosen by the finite state machine. The character replaces the existing sequence element. Note that the finite machine is provided the character on the tape as input but it doesn't get the tape head's location as input.
In addition to writing a character to the tape, the finite state machine's also outputs an element from a binary set which encodes whether the head should move left or right once it has finished writing at the current tape location. Usually this the set is described as containing the two characters 'L' and 'R'; L decrements the tape head position, R increments it. When the head is at the beginning of the tape, L has no effect.
Formal definition
The formal definition of a Turing machine builds off of the definition of a finite automata. The definition of finite automata is recalled here.
Finite automata
A finite automaton is a 5-tuple (\( Q, \Sigma, q_0, F, \delta \)), where:
1. \( Q \) is a finite set called the states,
2. \( \Sigma \) is a finite set called the alphabet,
3. \( q_0 \in Q \) is the start sate, and
4. \( F \subseteq Q \) is the set of accept states.
5. \( \delta : Q \times \Sigma \to Q \) is the transition function.
The definition of the Turing machine modifies the above definition of a finite automaton in three ways:
Specify a blank symbol
A symbol is introduces that is only present on the tape (it is not a symbol that can be present in the input). A Turing machine uses this symbol to, among other things, detect the end of the input once the input is placed on the tape.
Change to the transition function
Secondly, it modifies the transision function by increasing the dimensionality of its codomain. The codomain becomes \( Q \times \Gamma \times \{L, R\} \), where \( \Gamma \) is the set of symbols allowed on the tape and \( \{L, R\} \) is a set with two elements.
Introduction of a reject state
A reject state is similar to an accept state. The addition of a second type of ending state allows for the machine to end while indicating a sense of failure.
With these changes, the definition of a Turing machine looks like:
Turing machine
A Turing machine is parameterized as a 7-tuple, \( (Q, \Sigma, \Gamma, \delta, q_{accept}, q_{reject}) \), where \( Q, \Sigma \) and \( \Gamma \) are all finite sets, \( \delta \) is a function and \( q_{accept} \) and \( q_{reject} \) are elements of \( \Sigma \).
1. \( Q \) is the set of states of the machine's underlying finite state machine.
2. \( \Sigma \) is the input alphabet. It doesn't contain the blank symbol, ␣.
3. \( \Gamma = \Sigma \cup \{␣\} \) is the tape alphabet.
4. \( \delta : Q \times \Gamma \to Q \times \Gamma \times \{L, R\} \) is the transition function.
5. \( q_0 \in Q \) is the start state.
6. \( q_{accept} \in Q \) is the accept state.
7. \( q_{reject} \in Q \) is the reject state, where \( q_{reject} \ne q_{accept} \).
There is a number of ways to denote a Turing machine with a tuple of sets. All are functionally equivalent but differ in how much of the machines specification is included in the tuple. The above formulation closely follows the presentation of Michael Sipser. The reverse side contains a discussion of some of the issues with this and other definitions.
BackOnlyText: Inconsistency of the standard Turing machine 'definition'
The decision of what lies this Tuple seems a little arbitrary. There are many aspects of a Turing machine, such as the idea that the head of the tape can move either left or right, which don't appear in the definition above, yet are vital for it's behaviour. One could argue that the above definition isn't really a definition. If it is classed as a definition, then, assuming some prior definition, the above tuple should be a minimal set that describes all possible Turing machines parameterizations. However, this statement isn't entirely satisfactory, as the blank symbol could easily be removed from the tuple and placed in the prior definition, as all Turing machines posses it.
I'm also drawn to notice that the blank symbol could be placed in the tuple as a separate element, instead of as an element of \( \Gamma \), then define \( \Gamma \) as \( \Gamma = \Sigma \cup \{ b \} \).
I'm also curious as to why the set \( \{L, R\} \) is not properly defined: what are \( L \) and \( R \)? Are they the characters L and R, or are they variables? If they are variables, do they not belong in the definition like \( b \)? Or maybe \( b \) doesn't belong in the definition.
Yet another arbitrary choice is whether the accept and reject states are single elements of \( Q \) or whether they are subsets of \( Q \). Brilliant.org goes as far as to not define reject states, but to consider a halt and fail occuring if \( \delta \) is 'undefined' for some input. This seems like a terrible definition, as a function, by definition, is defined for all of it's domain.
Stanford's Plato philosophy wiki takes an extremely minimal approach and doesn't include the blank, accept or reject states in it's tuple (which thus becomes a 4-tuple). https://plato.stanford.edu/entries/turing-machine/
The conclusion of all of this is that it doesn't seem that there is a well agreed upon form of the definition (and whether definition is even the right word). Define it however you like in accordance with which objects you wish to manipulate easily.

Title: Turing-recognizable and Turing-decidable
The following four propositions are true:
Every Turing-decidable language is Turing-recognizable.
There exist Turing-recogniziable languages that are not Turing-deciable.
Every language can be recognized by multiple turing machines.
There does exist languages which are not Turing-decidable. There does exist languages that are not Turing-recognizable.
Every Turing machine has a language that it recognizes.
See the back for some explanations. The rest of this card builds up terminology used in the above propositions.
The concepts of recognizable and decidable rely on the concept of a configuration. The initial state of a Turing machine is typically described by a 7-tuple, but while operating, the head will move, and the tape will change, and a configuration is used to specify the current state of the tape and head.
Configurations
The tuple (FSM state, tape contents, tape head position) is called a configuration. Configurations are often written like so: 1011q_701111. This configuration represents a Turing machine with the the following state:
- the tape contents is '101101111'
- the state machine's state is q_7
- the head is at position 4 (over the rightmost 0).
Accept, reject or loop
The essence of the Turing machine is captured in the transition function, \( \delta \), as it shows how and with what limits the machine can change from state to state.
There are three outcomes possible after starting a Turing machine on an input:
1. the machine may end and accept the input string by entering state \( q_{accept} \),
2. the machine may end and reject the input string by entering state \( q_{reject} \),
3. or the machine may never end.
Comparison to finite automata
A noteworthy difference between Turing machines and finite automata is that finite automata stop once they have consumed the whole input. Turing machines can continue indefinitely after passing over all or only part of the input.
Languages reconized by a Turing machine
Let \(M = (Q, \Sigma, \Gamma, \delta, q_{accept}, q_{reject}) \) be a Turing machine. The collection of strings that \( M \) accepts is called the the language recognized by \( M \), or simply the language of \( M \), denoted \( L(M) \).
An alternative description of the above concept highlights the nature of the correspondence:
TM M recognizes language L iff:
1. The strings in L put M into the accept state.
2. The strings NOT IN L either:
  1. put M into the reject state, or
  2. cause M to loop.
The second type of language associated with a Turing machine:
Languages decided by a Turing machine
Let \(M = (Q, \Sigma, \Gamma, \delta, q_{accept}, q_{reject}) \) be a Turing machine that always halts (never loops). The collection of strings that \( M \) accepts is called the the language decided by \( M \).
Categorizing languages
Any language can be categorized as to whether there exists a Turing machine that recognizes it or not; similarly, all languages can be categorized as to whether there exists a Turing machine that decides it.
A language is called Turing-recognizable iff some Turing machine recognizes it.
Alternative terminology for Turing-recognizable language: recursively enumerable language.
A language is called Turing-decidable (or just decidable) iff some Turing machine decides it.
Alternative terminology for Turing-decidable language: recursive language.
Visualizing the space of languages divided by a Turing machine
Every decidable language is Turing-recognizable. Explanation.
Take any decidable language. By definition, there is a Turing machine that decides it. Replace all reject states with accept states [this sounds wrong....]. Now you have a Turing machine that accepts every string in the language. The reverse is not true. It is true that there exists languages that are recognizable but not deciable! See: this explanation, or the attached pdf (downloaded from here).
Multiple Turing machines per language. Explanation.
While each Turing machine has only 1 language that it recognizes and 1 language that it decides, a language can have multiple Turing machines that recognize or decide it. To see this, imagine making a change to a Turing machine that has no effect, like adding a state that is never reached.
Undecidable, unrecognizable
There are uncountably many languages, but only countable many Turing machines. As each Turing machine can only recognize a single language, there must be languages for which no Turing machine recognizes. Such languages are also not decided by any Turing machine.
A recognizer or a decider
A Turing machine can either recognize a lanugage decide a language, but not both. If there is any string for which the Turing machine doesn't halt, then that machine cannot decide any language. So a Turing machine is either a recognizer or a decider!
Turing machine, recap
A recap, below is a formal definition of a Turing machine:
Turing machine
A Turing machine is parameterized as a 7-tuple, \( (Q, \Sigma, \Gamma, \delta, q_{accept}, q_{reject}) \), where \( Q, \Sigma \) and \( \Gamma \) are all finite sets, \( \delta \) is a function and \( q_{accept} \) and \( q_{reject} \) are elements of \( \Sigma \).
1. \( Q \) is the set of states of the machine's underlying finite state machine.
2. \( \Sigma \) is the input alphabet. It doesn't contain the blank symbol, ␣.
3. \( \Gamma = \Sigma \cup \{␣\} \) is the tape alphabet.
4. \( \delta : Q \times \Gamma \to Q \times \Gamma \times \{L, R\} \) is the transition function.
5. \( q_0 \in Q \) is the start state.
6. \( q_{accept} \in Q \) is the accept state.
7. \( q_{reject} \in Q \) is the reject state, where \( q_{reject} \ne q_{accept} \).
The above 7-tuple describes the initial conditions of a Turing machine.
Source: Sipser, p170

Title: Subject map
Source: https://www.cs.helsinki.fi/u/jllang/Introduction_to_Lambda_Calculus_2020-02-20.pdf

Title: Examples of decidable and undecidable languages
Consider the decidability and recognizability of some specific languages. All the below languages represent answers to certain questions. If one of the languages is decidable, then the corresponding question can be answered definitively in finite time by a Turing machine.
The acronyms used below are:
DFA
Deteministic finite automaton
NFA
Non-deterministic finite automaton
CFG
Context free grammar
TM
Turning machine
Linear bounded machine
Linear bounded machine (TM with finite memory).
Given a DFA, \( B \), and a string, \( w \), does \( B \) accept \( w \)? | \( A_{\text{DFA}} = \{ \langle B, w \rangle | \text{$B$ is a DFA that accepts input string $w$} \} \) | Decidable
Given a NFA, \( B \), and a string, \( w \), does \( B \) accept \( w \)? | \( A_{\text{NFA}} = \{ \langle B, w \rangle | \text{$B$ is a NFA that accepts input string $w$} \} \) | Decidable
Given a CFG, \( G \), and a string, \( w \), does \( G \) generate \( w \)? | \( A_{\text{CFG}} = \{ \langle G, w \rangle | \text{$G$ is a CFG that generates input string $w$} \} \) | Decidable
Given a TM, \( M \), and a string, \( w \), does \( M \) accept \( w \)? | \( A_{\text{TM}} = \{ \langle M, w \rangle | \text{$M$ is a TM that accepts input string $w$} \} \) | Undecidable, but recognizable
Given a LBA, \( M \), and a string, \( w \), does \( M \) accept \( w \)? | \( A_{\text{LBA}} = \{ \langle M, w \rangle | \text{$M$ is a LBA that accepts input string $w$} \} \) | Decidable!
Given a DFA, \( B \), is the language of \( B \) empty? | \( E_{\text{DFA}} = \{ \langle B \rangle | \text{$B$ is a DFA and $\operatorname{L}(B) = \emptyset$} \} \) | Decidable
Given a CFG, \( G \), is the language of \( G \) empty? | \( E_{\text{DFA}} = \{ \langle G \rangle | \text{$G$ is a CFG and $\operatorname{L}(G) = \emptyset$} \} \) | Decidable
Given a TM, \( M \), is the language of \( M \) empty? | \( E_{\text{TM}} = \{ \langle M \rangle | \text{$M$ is a TM and $\operatorname{L}(M) = \emptyset$} \} \) | Undecidable
Given a LBA, \( M \), is the language of \( M \) empty? | \( E_{\text{LBA}} = \{ \langle M \rangle | \text{$M$ is a LBA and $\operatorname{L}(M) = \emptyset$} \} \) | Undecidable
Given two DFAs, \( A \) and \( B \), do they recognize the same language? | \( EQ_{\text{DFA}} = \{ \langle A, B \rangle | \text{$A$ and $B$ are DFAs and $\operatorname{L}(A) = \operatorname{L}(B)$} \} \) | Decidable
Given two CFGs, \( A \) and \( B \), do they recognize the same language? | \( EQ_{\text{CFG}} = \{ \langle A, B \rangle | \text{$A$ and $B$ are CFGs and $\operatorname{L}(A) = \operatorname{L}(B)$} \} \) | Undecidable
Given two TMs \( M_1 \) and \( M_2 \), do they recognize the same language? | \( EQ_{\text{CFG}} = \{ \langle M_1, M_2 \rangle | \text{$M_1$ and $M_2$ are TMs and $\operatorname{L}(M_1) = \operatorname{L}(M_2)$} \} \) | Undecidable
Given a Turing machine, \( M \), does it halt on a given input? | \( HALT_{\text{TM}} = \{ \langle M, w \rangle | \text{$M$ is a TM and accepts or rejects $w$} \} \) | Undecidable
Given a Turning machine \( M \), does it recognize the same language as a DFA? | \( REGULAR_{\text{TM}} = \{ \langle M \rangle | \text{$M$ is a TM and $\operatorname{L}(M)$ is a regular language.} \} \) | Undecidable
BackOnlyText: Interesting point: the complement of \( A_{\text{TM} } \), \( \overline{A_{\text{TM} } } \), isn't even recognizable!

Title: Language and Turing machine visualization
FrontDescription: Can you remember a visualisation that connects languages and Turing machines? It also includes the language representing the question of whether an arbitrary Turing machine accepts some input.

Title: Number theory is undecidable
Q: Mathematical model
An alphabet \( \land, \lor, \lnot, (,), \forall, \exists, x_1, x_2, ..., R_1, ... R_k \) has a model which is a tuple \( (U, P_1, ... P_k) \) where \( U \) is the universe from which variables may take values and \( P_1, ... P_k \) are the relations assigned to the symbols \( R_1 ... R_k \).
A formula is recursively defined starting from atomic formula and building from here with the \( \land, \lor, \lnot, \forall\) and \( \exists \) symbols.
The language of a model is the collection of formulas but restricted to those that only use the relations listed in the model.
The theory of a model is the collection of true sentences in the language of that model.
Decidable theory
For a model, \( \mathcal{M} \), its theory \( \operatorname{Th}(\mathcal{M}) \) is said to be a decidable theory iff there exists [what?] that can [what?].
\( \operatorname{Th}(\mathbb{N}, +) \) is decidable
The model constructed from the logic symbols along with the natural numbers and the addition relation—the theory for this model is decidable.
\( \operatorname{Th}(\mathbb{N}, +, \times) \) is undecidable
The model constructed from the logic symbols along with the natural numbers and the addition and multiplication relation—the theory for this model is not decidable.
The proof idea of the undecidability of number theory is on the reverse side. Can you remember the rough idea?
A: an algorithm (Turing machine); decide if a statement constructed according to the model is true or false
BackOnlyText: \( \operatorname{Th}(\mathbb{N}, +, \times) \) is undecidable. Proof idea.
The idea is to show that if the theory was decidable, we could determine whether an arbitrary Turing machine accepts some arbitrary input!
For a given Turing machine and input, it's possible to construct a statement according to the model such that the statement is true iff the machine accepts the input. Now a fact: we can enumerate all proofs possible in the model. With this we will eventually find a proof for the statement and thus determine whether the machine accepts the input. But this is impossible! We would have just created an algorithm to determine if a Turing machine accepts an input! The catch is that we assumed that there was a proof for the statement to be either true or false. The line of reasoning in the detailed proof implies that there are statements in the model that have no proof for either truth or falsity.

Title: Context-free languages
Context-free languages
A context-free language is a language that can be generated by some context-free grammar.
Below, we define the pieces involved in this definition.
Grammar
A grammar can be considered an input datum of a specific type of string rewrite system that takes in input in the form of a list of production rules.
Below are some examples of some production rules:
\[ \begin{align*} S &\to aSb && (\text{context-free}) \\ S &\to AB && (\text{context-free}) \\ aA &\to C && (\text{not context-free}) \\ bAc &\to B && (\text{not context-free}) \\ CA &\to cA && (\text{not context-free}) \\ \end{align*} \]
A context-free grammar is one type of grammar.
Context-free grammar (my definition)
A grammar is context-free iff all production rules have a LHS consisting of a single symbol.
See the back side for the standard definition and an explanation as to why I think it contains redundancies.
A quality of context-free grammars is that no matter what order rewrites are carried out, the same language will be generated.
The implicit grammar machine
In my opinion, the concept of a context-free grammar cannot be defined without reference to the machine that takes the rules as input and carries out the re-writes. The way the rules are written strongly hint as to the operation of the machine taking them as input. I make some more remarks about this on the back side.
BackOnlyText: Standard definition
The following is a more typical definition of a context-free grammar.
Context-free grammar (standard definition)
A grammar is context-free iff all production rules have a LHS consisting of a single non-terminal symbol.
I think this definition is superfluous in its reference to terminal symbols. Any production rule set with only single symbols on the LHS implicitly defines it's "non-terminal" symbols as all such LHS symbols. Thus, there is no need for defining any notion of terminal/non-terminal symbols.
The below section is some thoughts on flaws of common formal definitions of context-free grammars.
The implicit grammar machine
Grammars are often discussed without making explicit the fact that an algorithm for generating strings is being described. A grammar is the input to one of these machines, and so one can't properly describe a grammar without describing how the machine works. The Sipser book and the Hopcroft book both fail to explicitly identify the algorithm they are relying on, and consequently, their definition of a grammar contains seemingly redundant variables.
My attempt at a medium level description of a grammar machine is that it is a string rewrite system of the following form. The machine takes in a list of tuples of the form [(string1, string2), (string1, string2), ...]. The first tuple is expected to be the starting rule which will kick-start the string generation loop. An initially empty list of intermediate string is maintained. The second string in the first tuple is added to this intermediate list. Then, the following loop continues until a loop has no effect: loop over every intermediate string, loop over every tuple, carry out a rewrite if a tuple's first string matches a substring in the input and add the generated string back to the intermediate list of strings. The resulting intermediate list of strings becomes the output.
In order for the machine to function correctly, the input will need to be encoded according to whatever encoding is expected. This encoding will place some restrictions on the tuples. For example, for a machine that works only with context-free grammars, the first string of each tuple must be a single symbol; this insures that the rule has no context and that the symbol will never appear in the output strings.
With this type of definition, the definition by Sipser seems to includes unnecessary components: variables, terminals and the start variable. Moving these quantities into the definition of the machine does not detract from the generality of the machine and cleans up the definition of a grammar.
Context-free languages vs regular languages
The three main concepts are context-free grammars, context-free languages and pushdown automata. In my opinion, what context-free grammars are are input to a program that generates a context-free language. In this way, grammars paired with the implicitly described machine is a generating machine while the pushdown automata is a deciding machine. When compared to finite automata, context-free languages are to regular languages, pushdown automata are to non-deterministic finite state machines, and there isn't an obvious equivalent of context-free grammars. One attempt to find an equivalent concept to context-free grammars is to consider an algorithm that moves over a finite state machine in a depth-first or breath-first manner and generates all strings of the language.
An interesting remark about the above comparison between regular and context-free languages is that pushdown automata do not have an equivalently powerful non-deterministic variant. Instead, a non-deterministic pushdown automata is distinctly less powerful and cannot decide all context-free languages. This raises an interesting question as to whether maybe there is an important intermediate language type between regular and context-free languages.
Context: grammar → context-free grammar → context-free language → context-free language closure → Chomsky normal form → pushdown automaton → deterministic pushdown automaton

Title: Chomsky normal form
Q: Context-free grammars can differ in their rule sets yet generate the same language. From the set of such equivalent grammars, some are easier to reason about.
One type of context-free grammar that is convenient to work with is the Chomsky normal form.
Chomsky normal form
A context-free grammar is in Chomsky normal form iff the RHS of every rule is either:
1. two symbols that [what?], or
2. one symbol that [what?].
The above definition is non-standard. The more common definition is on the back side.
There is an important theorem regarding Chomsky normal form below. Can you remember it?
Any context-free language is generated by a context-free grammar in Chomsky normal form.
A: both appear as LHS symbols in another rule excluding the start rule; does not appear as a LHS symbol
BackOnlyText: Chomsky normal form (standard definition)
A context-free grammar is in Chomsky normal form iff every rule is of the form:
\[ \begin{align*} S &\to BC \\ S &\to a \\ A &\to BC \\ A &\to a \\ \end{align*} \]
where \( a \) is a terminal symbol, \( S \) is the start symbol and \( A, B \) and \( C \) are non-terminal symbols.
It is assumed that \( \varepsilon \) can appear on the RHS of a rule.
Context: grammar → context-free grammar → context-free language → context-free language closure → Chomsky normal form → pushdown automaton → deterministic pushdown automaton

Title: Context-free languages: closed operations
Context-free language closure
If \( L \) and \( M \) are context-free languages, then the following are also context-free languages:
- \( L \cup M \)
- \( L \circ M \)
- \( L^{\star} \)
In other words, context-free languages are closed under union, concatenation and Kleen star.
There are important operations under which context free languages are not closed. Can you remember them?
BackOnlyText: Context-free languages are not closed under:
- intersection
- complementation
- set difference
Context: grammar → context-free grammar → context-free language → context-free language closure → Chomsky normal form → pushdown automaton → deterministic pushdown automaton