#Computation Models

Here is the writeup note from Computation Models I took at University of California Santa Cruz. Here is the textbook I have referred for most. If any further understanding is needed, I would highly recommend fact checking on this material.

#Problem Representation and Decision Process

We are going to study on decision problems. But first thing first, let's review couple of decision process definitions. Those notations are very crucial on learning regular languages.

1. Instance of Problem

• Input: An instance of the problem is provided.
• Output: The question checks if the instance has a specific property.

2. Notation and Definitions

• $\Sigma$: Alphabet set of symbols
• x $\in$ $\Sigma$*: A string over the alphabet $\Sigma$
• L $\subseteq$ $\Sigma$*: A language set of strings

---

#Set Operation

What Is a Set? A set is a collection of distinguishable objects. We often denote membership with the symbol “∈” (e.g., $x \in S$).

• Intersection: $A \cap B$ Elements that are in both $A$ and $B$.
• Union: $A \cup B$ Elements that are in $A$ or $B$ (or both).
• Difference: $A - B$ Elements in $A$ that are not in $B$.
• Symmetric Difference: $A \,\Delta\, B$ Elements that are in $A$ or $B$, but not in both.

---

#Russell’s Paradox and Logical Consistency

Russell’s Paradox from set theory showed that allowing self-referential sets leads to contradictions. If contradictions are allowed, anything can be proven true. A take away from this theory is that to avoid contradictions to keep logic valid.

---

#Induction

To prove a statement using strong induction, we show:

1. Base Cases:
   Prove that $S(1), S(2), \dots, S(k)$ are true.
2. Inductive Step:
   Assume that $S(1), S(2), \dots, S(m-1)$ are true for $m > k$, and prove that $S(m)$ is also true.

---

#Closure Property

• Closure
• Complement
• Intersection
• Union
• Difference
• Concatenation
• Kleene Star
• Reversal

#Regular Expression

Syntax	Semantics
$\epsilon$	$L(\epsilon) = \{\epsilon\}$
$\emptyset$	$L(\emptyset) = \emptyset$
$a$	$L(a) = \{a\}$
$r_1 + r_2$	$L(r_1 + r_2) = L(r_1) \cup L(r_2)$
$r_1 \cdot r_2$	$L(r_1 \cdot r_2) = L(r_1) L(r_2)$
$r^\ast$	$L(r^\ast) = \bigcup\_{i=0}^{\infty} L(r)^i$

---

#Finite Automaton

#Deterministic Finite Automaton (DFA)

A DFA processes an input string symbol-by-symbol, transitioning between states according to $\delta$. If the DFA ends in an accept state, it accepts the string; otherwise, it rejects it. Language accepted by a DFA: The set of all strings that lead to an accept state. A language is regular if and only if there exists a DFA that accepts it. A DFA is a formal model of computation defined as a 5-tuple:

$$M = (Q, \Sigma, \delta, q_0, F)$$

Where:

• $Q$: A finite set of states.
• $\Sigma$: A finite alphabet (set of input symbols).
• $\delta$: A transition function $\delta: Q \times \Sigma \to Q$ that determines the next state.
• $q_0$: A start state, which is an element of $Q$.
• $F$: A set of accept states (a subset of $Q$), indicating when the DFA accepts a string.

#Non-Deterministic Finite Automaton (NFA)

An NFA is similar to a DFA in that it is a formal model of computation for recognizing regular languages. However, it differs in its ability to have multiple (or even zero) possible transitions for a given state and input symbol. In an NFA, if any computational branch (path) leads to an accept state when the entire input is read, the NFA accepts the string. An NFA is defined as a 5-tuple:

$$M = (Q, \Sigma, \delta, q_0, F)$$

Where:

• $Q$: A finite set of states.
• $\Sigma$: A finite alphabet of input symbols.
• $\delta$: A transition function $$\delta: Q \times (\Sigma \cup \{\varepsilon\}) \to 2^Q$$ This function assigns to each state and input symbol (or the empty string $\varepsilon$) a set of possible next states.
• $q_0$: The start state, an element of $Q$.
• $F$: A set of accept states (a subset of $Q$).

Practice: Converting from NFA to DFA

Convert this NFA to an equivalent DFA. Provide only the portion of the DFA reachable from the start state.

Based on the concept of DFA construction, create the following transition table. Each DFA state corresponds to a set of NFA states, representing all possible NFA states reachable simultaneously. Analyze each DFA state by determining transitions for inputs (0) and (1):

DFA State	Moves on (0)	Moves on (1)
({x_0})	({x_1, x_4, x_6})	—
({x_1, x_4, x_6})	({x_2, x_4})	({x_3, x_5})
({x_2, x_4})	({x_4})	({x_3, x_5})
({x_3, x_5})	({x_3})	({x_0, x_3})
({x_4})	({x_4})	({x_5})
({x_3})	({x_3})	({x_0, x_3})
({x_0, x_3})	({x_1, x_4, x_6})	({x_0})

An NFA accepts a string if it reaches at least one accept state in its subset of current states. Given that ( x_0 ) and ( x_3 ) were accept states in the original NFA, any DFA state containing ( x_0 ) or ( x_3 ) becomes an accept state.

#Two-Way Finite Automata (2WFA)

A 2DFA extends the DFA model by allowing the input head to move in both directions—left and right—on the input tape. This added movement can sometimes result in a more succinct description of a language, although it still recognizes only regular languages. A 2DFA is defined as a 6-tuple:

$$M = (Q, \Sigma, \delta, q_0, F, \triangleright)$$

Where:

• $Q$: A finite set of states.
• $\Sigma$: A finite alphabet of input symbols.
• $\delta$: A transition function $$\delta: Q \times (\Sigma \cup \{\triangleright, \triangleleft\}) \to Q \times \{L, R\}$$ This function determines both the next state and the direction (Left or Right) in which the head moves. (Often, special markers such as $\triangleright$ and/or $\triangleleft$ are used to denote the left and right boundaries of the input tape.)
• $q_0$: The start state, an element of $Q$.
• $F$: A set of accept states (a subset of $Q$).
• Input Tape and Markers: The input is placed on a tape bounded by special symbols (end markers) that the head cannot move past.

#Pushdown Automaton (PDA)

Pushdown Automaton (PDA) designed to accept the language:

$$L = \{a^i b^j c^k \mid i, j, k \geq 0 \text{ and } (i = j \text{ or } i = k) \}$$

This language includes strings of the form (a^i b^j c^k), where the number of (a)'s is equal to the number of (b)'s or the number of (a)'s is equal to the number of (c)'s. This is a non-context-free language and is accepted by a PDA that uses its stack to track and compare the number of symbols.

---

#Context-Free Languages (CFL)

#Key Properties

• All regular languages are CFLs.
• Example: ({ 0^m 1^m \mid m \geq 0 }) is a CFL.
• Palindromes are CFLs.
• Example of a non-CFL: ({ a^m b^m c^m \mid m \geq 3 })

#Context-Free Grammar (CFG)

A CFG is defined as:

$$G = (N, \Sigma, P, S)$$

where:

• $N$: Finite set of non-terminals (variables)
• $\Sigma$: Finite set of terminals
• $P$: Finite subset of $N \times (N \cup \Sigma)^\ast$ set of productions/rules
• $S \in N$: Start symbol

---

#Chomsky Normal form

Chomsky Normal Form (CNF) is a specific type of formal grammar structure primarily used in the theory of context-free grammars (CFGs). It simplifies the structure of CFGs to a standardized form, which helps in algorithms, proofs, parsing techniques, and theoretical analysis.

It is notably useful for algorithms like the CYK (Cocke–Younger–Kasami) parsing algorithm. A CFG is said to be in Chomsky Normal Form if every production rule is of exactly one of the following forms:

1. $A \rightarrow BC$
   (Exactly two non-terminal symbols on the right-hand side)

2. $A \rightarrow a$
   (Exactly one terminal symbol on the right-hand side)

Additionally, if the language generated includes the empty string ($\varepsilon$), then the grammar may include the rule:

3. $S \rightarrow \varepsilon$
   (Only allowed if $S$ is the start symbol, and it must not appear on the right-hand side of any rule.)

---

#CKY algorithm

• Parsing Algorithms: The CKY Algorithm
  • The CKY algorithm is a dynamic programming method used for parsing strings in a context-free language.
  • Key Points:
    • The grammar must be converted to Chomsky Normal Form (CNF), where production rules are either:
      • A variable goes to two variables, or
      • A variable goes to a single terminal.
    • The algorithm fills a table (or triangular matrix) where each cell represents the set of variables that can generate the substring corresponding to that cell.
    • The string is accepted if the start symbol appears in the cell representing the entire string.
    • Although the naive approach for checking membership might be exponential, the CKY algorithm runs in cubic time relative to the length of the input.

---

#Turing Machines

• The Turing Machine is the most powerful computational model we will consider.
• It was invented by Alan Turing in 1936.
• The concept was developed before modern computers, to formalize the idea of an algorithm.

#Defining Computability

A Turing Machine is defined as a 7-tuple:

$$(Q, \Sigma, \Gamma, \delta, q*0, q*{\text{accept}}, q\_{\text{reject}})$$

Where:

• $Q$ = Finite set of states
• $\Sigma$ = Input alphabet
• $\Gamma$ = Tape alphabet (includes $\Sigma$ and additional symbols like blank)
• $\delta$ = Transition function:
  • $\delta(q, x) = (q', y, D)$, where:
    • $q'$ = next state
    • $y$ = symbol to write
    • $D$ = direction (left or right)
• $q_0$ = Start state
• $q\_{\text{accept}}$ = Unique accept state
• $q\_{\text{reject}}$ = Unique reject state

#Basic Turing Machine Structure

• Infinite Tape: Unlike finite-state machines, the Turing machine has an infinite tape.
• Read/Write Head:
  • Can move left or right.
  • Can write new symbols (unlike DFAs, which only read).
• Finite Control: Determines state transitions based on the current symbol.
• Accept/Reject States:
  • Unique accept state and reject state.
  • Once entered, the machine halts.

---

#List of proof

#Myhill-Nerode Theorem

Let ( L \subseteq \Sigma^\ast ). The following two statements are equivalent:

1. ( L ) is a regular language.
2. The index (number of equivalence classes) of ( R_L ) is finite.

This theorem provides a necessary and sufficient condition for a language to be regular. If the equivalence relation ( R_L ) partitions the strings into finitely many equivalence classes, then ( L ) is regular. Conversely, if ( L ) is regular, then ( R_L ) has a finite number of equivalence classes.

---

#Appendix

Equivalence Relation

• The index of an equivalence relation is the number of distinct equivalence classes in ( A ).

同値類とは？(equivalence class) → 関係 ( R ) によって「同じ」とみなされる要素の集合。
同値類の性質(Properties of equivalence classes) → 同値類は「同じ」か「完全に異なる（重ならない）」。
集合の分割(Partition of a set) → 集合全体は同値類の和集合として表せる。
指数とは(index (of an equivalence relation)?)？ → 同値類の個数のこと。