Undergrad notes

Philosophy of mathematics

The geometry you did in high school is the virtue of one man- Euclid of Alexandria. The man, in 300 BC, introduced five postulates and single handedly built the field of geometry on them. His work was so elegant that it took us 20 centuries to realize that tweaking of one of his postulate can lead to new ideas, what we now call the ‘non-Euclidean’ geometries. Following the philosophical footsteps of Euclid, David Hilbert introduced a program which was intended to be axiomatization of, not just of the new geometries, but of all of mathematics. It was certainly the hardest task a man had ever taken.

What real maths look like

The mathematicians working on the program needed to formalize the notion of ‘effectively calculable functions’ to describe what a ‘mathematical proof’ means. They had intuitive sense that the method or procedure to calculate such functions had to be mechanically feasible. All the naturally occurring functions: polynomials, rationals, trigonometrics, exponentials would fall under this class because if there is a natural phenomena related to a function, one could devise a calculable machine based on the physics of it. Beside these, there could be numerous other functions, some even unknown to mankind. To encapsulate all of them is a daunting task. The problem is essentially this:

If you give me a function f, I will, probably, tell you whether f should lie in the class S or not.

Give me a concise definition of the class S.

Such problems are what they encounter in ‘real life’ mathematics which gives you a lot of freedom to exercise your creativity. It is, in fact, exactly opposite to the ‘university’ way of doing mathematics:

Here is the definition of class S.

Will you tell me whether the function f falls on the class S?

I felt proud when I proved sin(x) to be continuous at x = 0 using ϵ-δ definition of continuity. But real genius was the guy who came up with it.

Now there are probably two ways you could approach this problem:

Define a class S and claim the procedures that calculate functions in S to be ‘effective methods’

Construct an ultimate mechanical machine ‘M’ and claim functions calculable by M to be ‘effectively calculable’

Rise of two young men A young Kurt Godel (o with double dot) preferred the first one. He formalized the definition of the class of general recursive functions: the smallest class of functions that would capture the intuitive notion of effectively calculable functions.

Another young man named Alan Turing used the second approach to come up with a mathematical (but mechanically possible) model of an ultimate machine that does nothing but manipulates symbols on a strip of tape according to a table of rules. The set of functions calculable by this machine, now called Turing machine, is precisely the class of general recursive function defined by Godel.

The equivalency of these definitions suggest a mechanical upper limit to the notion of ‘computability’. Note I am emphasizing on the ‘mechanicality’, for some words are in order when Turing machine gets quantum (that’s the story for another letter). Let’s get bold and define computability.

effectively calculable functions (informal notion) = general recursive functions (Godel’s definition) = ‘computable functions’ (formal notion)

effective methods or procedures (informal notion) = turing machine (Turing’s definition) = ‘algorithms’ (formal notion)

The Godel’s and Turing’s ideas act as the bridge between the informal and formal notion of effective calculability. Although this claim of computability has near-universal acceptance, it cannot be formally proven as the concept of effective calculability is only informally defined.

People have experimented with Turing machines, equipping it with multiple tapes, nondeterminism and so on. They could only come up with machines that compute faster or use less memory but they cannot compute more powerfully (i.e. more mathematical functions). Thus, the claim still stands, and will very likely keep standing.

Modern computers The ‘Universal Turing machine’ is a variant of the original Turing machine that simulates an arbitrary Turing machine on arbitrary input. The universal machine essentially achieves this by reading both the description of the machine to be simulated as well as the input to that machine from its own tape.

The Universal Turing machine seems to compute all that is possible. So, solving problems would be easier if people had such machines in their offices. Unfortunately such machines are hardly feasible, even if you could build them, programming such machines would be no easy task. In this context, programming would be to encode a Turing machine into a tape and feed it to the Universal Turing machine.

Turing himself and many authors investigated equivalent machines that could be brought into practice. Building upon the work on Turing, John von Neumann devised the concept of a stored program machine. As far as computational capability, Turing machines and von Neumann machines are equivalent. Either one can emulate the other. The modern digital computers are just sophisticated von Neumann machines. Charles Babbage is said to have anticipated the idea a century earlier.

So, if any, modern computer science has three full fathers.

Non-computability The natural question to ask is ‘what are those functions that are out of reach of mechanical computation?’. The answer is the following decision problem:

f(M, w) = Given a Turing machine M, will it halt on the input w?

This function and other functions reducible to it are uncomputable. That is to say, there is no algorithm which will tell you whether the given Turing machine will halt on an arbitrary input. You could devise a hypothetical oracle that would possibly answer that question, but again there would be no recipe to construct it mechanically.

Are you Turing complete? In general when people talk about models that are near the Turing machines, they use following terminologies:

A model is Turing-complete if it is at least as powerful as Turing machines.

A model is Turing-equivalent if it is exactly as powerful as Turing machines.

An example of a Turing-complete system which is not Turing equivalent is Turing machines with oracle access to an oracle for the halting problem. The Turing equivalency or completeness does not necessarily mean that you can build mechanical version of such models. The physically implementable Turing-complete systems are Turing-equivalent, which aids our claim of computability.

Powerful than a Turing machine The modern digital computers are, in a form of abstraction, von Neumann machines. However, the actual physical devices are built from electronics circuits. The circuit model which consists the multiset of universal gates such as {AND, NOR, NOT} are Turing equivalent and nearer to real computers.

Furthermore, if you allow the circuits to have to be ‘infinite’ they can solve the halting problem. So, infinite circuits are in some sense ‘too powerful’ but they’re not realistic.

What else are Turing complete? To show that something is Turing-complete, it is enough to show that it can be used to simulate some Turing-complete system. For instance, an imperative language like C is Turing-complete if it has conditional branching (e.g., ‘if’ and ‘goto’ statements) and the ability to change an arbitrary amount of memory. If the limitation of finite memory is ignored, most modern programming languages are otherwise Turing-complete. Some softwares are Turing-complete by accident, i.e. not by design include Microsoft Powerpoint, Microsoft Excel, x86 MOV instruction.

Practical computability Turing machines are also helpful in establishing the notion of effective computability i.e. the set of problems that are solvable practically with limited resources. The resource DTIME, which is the computation time for a deterministic Turing machine, is used to define complexity classes, sets of all of the decision problems which can be solved using a certain amount of computation time. If a problem of input size n can be solved in O(f(n)), we have the complexity class DTIME(f(n)).

The well-known complexity class P comprises all of the problems which can be solved in a polynomial amount of DTIME.

A much larger class using deterministic time is EXPTIME, which contains all of the problems solvable using a deterministic machine in exponential time.

The complexity class NTIME(f(n)) is the set of decision problems that can be solved by a non-deterministic Turing machine which runs in time O(f(n)).

The NP is the set of decision problems can be solved in polynomial time by a nondeterministic Turing machine in polynomial time or alternatively have proofs verifiable in polynomial time by a deterministic Turing machine.

Million dollar question Since we have already established that a simple Turing machine can simulate the nondeterministic Turing machine in totality (regardless of the resources), isn’t it obvious that P = NP? I mean you just add the resource constraint into the equation. Rephrasing the question:

Can a polynomially bounded Turing machine simulate the steps of polynomially bounded non-deterministic Turing machine in polynomial time? Or,

Can a problem verifiable in polynomial time is also solvable in poynomial time?

It turns out that our civilization is not yet capable of answering such questions. Nevertheless we have managed to establish a set of specific problems called NP-hard such that, finding a polynomial time algorithm to solve any NP-hard problem would give polynomial time algorithms for all the problems in NP. Hence prove P=NP. An equivalent definition is to require that every problem in NP can be solved in polynomial time by an oracle machine capable of solving a NP-hard problem.

Some NP-hard problems are themselves in NP, such are called NP-complete, like the infamous 3SAT while there are decision problems that are NP-hard but not NP-complete such as the halting problem.

\documentclass[12pt]{report} \setcounter{tocdepth}{5} \setcounter{secnumdepth}{5} \usepackage{wrapfig} \usepackage{amssymb} \usepackage{tikz} \def\checkmark{\tikz\fillscale=0.4 — (.25,0) — (1,.7) — (.25,.15) — cycle;} \usepackage{multirow,tabularx} \usepackage{geometry} \geometry{ a4paper, total={170mm,257mm}, left=20mm, top=20mm, } \usepackage{calligra} \DeclareMathAlphabet{\mathcalligra}{T1}{calligra}{m}{n} \DeclareFontShape{T1}{calligra}{m}{n}{←>s*[2.2]callig15}{} \newcommand{\scripty}[1]{\ensuremath{\mathcalligra{#1}}} \usepackage{bm} \newcommand{\uvec}[1]{\hat{#1}} \setlength{\footskip}{45pt} \renewcommand{\familydefault}{\sfdefault} \usepackage{float} \usepackage{sfmath} \usepackage{parskip} \usepackage{graphicx} \usepackage{amsmath} \everymath{\displaystyle} \begin{document} \tableofcontents \chapter{Prequesities} \section{Terminologies} \begin{enumerate} \item {[Sets: Cartesian Products, Ordered Pairs, 3Cardinality, Relations: Graphs, Tables,]} \item {[Specifics: Reflexive, Symmetric, Transitive, Equivalence, Partial Order: Totality]} \item {[Alphabets $\Sigma$, Universe ${\Sigma }^{\ast }$, Language $\in {\Sigma }^{\ast }$, ofSets, Concat, Kleene [$0|>$], Plus [$1|>$]]} \item {[Finite Representations: Recognizers: "$w\in L?$";Generators: "$f\to w$"]} \end{enumerate} \section{Proof Techniques} \begin{enumerate} \item {[Proof By Contradiction]}\par [“For a proposition P :] \begin{enumerate} \item {[Assume P to be false,]} \item {[Prove that falsation of P implies two mutually contradictory assertions]} \end{enumerate} {[Hence the assumption that P is false must be wrong, so it is true”]} \item {[Proof By Induction]}\par [“For a statement $P(n)$ of N,] \begin{enumerate} \item {[Prove that $P(n)$ holds for $n=0$ or $n=1$, ie $P(0)$ or $P(1)$ is true,]} \item {[Assume that $P(n)$ holds for an arbitrary $n$ then prove that it holds for $n+1$]} \end{enumerate} [Hence these steps establish that $P(n)$ holds for every natural number”] \item {[Pigeonhole Principle:]}\par [“if $A$ and $B$ are finite sets, $|A|>|B|$ then there is no one-to-one function from $A$ to $B$”]\par [“if n birds are put into m holes, $n>m$ then, at least one hole contains more than one bird”] \item {[Diagonalization]}\par [“For a $R$ on $A$, D $\{a:a\in A,(a,a)\notin R\}$ is diff from each $R_a[a\in A]$$\{b:b\in A,(a,b)\in R\}$]\par [“The complement of a diagonal is different from each row”] \end{enumerate} \chapter{Automata Theory} \section{Finite Automata} {\bfseries [Informal:]} \par \par[a self-propeller with finite states that follows predefined sequence of operations automatically]\par {\bfseries [Formal:]} \par {[a DFA is a quintuple $M=(K,\Sigma ,\delta ,s,F)$ where]} \begin{enumerate} \item {[$K$ is a finite set of states]} \item {[$\Sigma$ is an alphabet}] \item {[$\delta$ is the transition function from $K\times \Sigma$ to $K$]} \item {[$s\in K$ is the initial state]} \item {[$F\subset K$ is the set of final states]} \end{enumerate} [a string in $w\in {\Sigma }^{\ast }$ is said to be accepted if and only if there is a state $q\in F$ such $(s,w){⊢}_M^{\ast }(q,e)$] \par[as ${⊢}_M^{\ast }$ is reflexive, transitive closure of the single move binary relation ${⊢}_M:K\times {\Sigma }^{+}\to K\times {\Sigma }^{\ast }$] \begin{table}[H] \def\arraystretch{1.3} \centering ~~~~~~~\begin{tabular}{|p{1cm}|p{1cm}|p{1cm}|} \hline $K^{\prime }s$ & $\Delta 0$ & $\Delta 1$\\hline $\to s$ & $q_1$ & $...$\\hline $q_1$ & $...$ & $\ast F$\\hline \end{tabular} \end{table} \subsection{Drawing Minimal DFAs}\par [Put yourself in place of the machine] \begin{enumerate} \item {[Present the crucial information of the language as minimum finite set of possibilities]} \item {[Next assign transitions as they go from one possibility to another upon reading symbols]} \item {[Might as well, interpret the language as the complement of another language]} \end{enumerate} {[\bfseries Length:]}\par \begin{enumerate} \item {[mod counter]} \begin{center} \begin{tikzpicture}[scale=0.2] \tikzstyle{every node}+=[inner sep=0pt] \draw [black] (8.9,-20.3) circle (3); \draw (8.9,-20.3) node {$1$}; \draw [black] (8.9,-20.3) circle (2.4); \draw [black] (21.2,-20.3) circle (3); \draw (21.2,-20.3) node {$2$}; \draw [black] (32.5,-20.3) circle (3); \draw (32.5,-20.3) node {$....$}; \draw [black] (44,-20.3) circle (3); \draw (44,-20.3) node {n}; \draw [black] (35.5,-20.3) — (41,-20.3); \fill [black] (41,-20.3) — (40.2,-19.8) — (40.2,-20.8); \draw (38.25,-20.8) node [below] {$0,1$}; \draw [black] (11.9,-20.3) — (18.2,-20.3); \fill [black] (18.2,-20.3) — (17.4,-19.8) — (17.4,-20.8); \draw (15.05,-20.8) node [below] {$0,1$}; \draw [black] (24.2,-20.3) — (29.5,-20.3); \fill [black] (29.5,-20.3) — (28.7,-19.8) — (28.7,-20.8); \draw (26.85,-20.8) node [below] {$0,1$}; \draw [black] (41.988,-22.522) arc (-45.99837:-134.00163:22.367); \fill [black] (10.91,-22.52) — (11.14,-23.44) — (11.83,-22.72); \draw (26.45,-29.3) node [below] {$0,1$}; \draw [black] (3.9,-20.3) — (5.9,-20.3); \fill [black] (5.9,-20.3) — (5.1,-19.8) — (5.1,-20.8); \end{tikzpicture} \end{center} \item {[greater than equals]} \begin{center} \begin{tikzpicture}[scale=0.2] \tikzstyle{every node}+=[inner sep=0pt] \draw [black] (9.7,-20.3) circle (3); \draw (9.7,-20.3) node {$1$}; \draw [black] (21.4,-20.3) circle (3); \draw (21.4,-20.3) node {$2$}; \draw [black] (32.5,-20.3) circle (3); \draw (32.5,-20.3) node {$....$}; \draw [black] (44,-20.3) circle (3); \draw (44,-20.3) node {$n+1$}; \draw [black] (44,-20.3) circle (2.4); \draw [black] (35.5,-20.3) — (41,-20.3); \fill [black] (41,-20.3) — (40.2,-19.8) — (40.2,-20.8); \draw (38.25,-20.8) node [below] {$0,1$}; \draw [black] (12.7,-20.3) — (18.4,-20.3); \fill [black] (18.4,-20.3) — (17.6,-19.8) — (17.6,-20.8); \draw (15.55,-20.8) node [below] {$0,1$}; \draw [black] (24.4,-20.3) — (29.5,-20.3); \fill [black] (29.5,-20.3) — (28.7,-19.8) — (28.7,-20.8); \draw (26.95,-20.8) node [below] {$0,1$}; \draw [black] (4.7,-20.3) — (6.7,-20.3); \fill [black] (6.7,-20.3) — (5.9,-19.8) — (5.9,-20.8); \draw [black] (46.68,-18.977) arc (144:-144:2.25); \draw (51.25,-20.3) node [right] {$0,1$}; \fill [black] (46.68,-21.62) — (47.03,-22.5) — (47.62,-21.69); \end{tikzpicture} \end{center} \item {[equals]} \begin{center} \begin{tikzpicture}[scale=0.2] \tikzstyle{every node}+=[inner sep=0pt] \draw [black] (9.1,-20.3) circle (3); \draw (9.1,-20.3) node {$1$}; \draw [black] (21.2,-20.3) circle (3); \draw (21.2,-20.3) node {$2$}; \draw [black] (32.5,-20.3) circle (3); \draw (32.5,-20.3) node {$....$}; \draw [black] (44,-20.3) circle (3); \draw (44,-20.3) node {$n+1$}; \draw [black] (44,-20.3) circle (2.4); \draw [black] (55.3,-20.3) circle (3); \draw (55.3,-20.3) node {$D$}; \draw [black] (35.5,-20.3) — (41,-20.3); \fill [black] (41,-20.3) — (40.2,-19.8) — (40.2,-20.8); \draw (38.25,-20.8) node [below] {$0,1$}; \draw [black] (12.1,-20.3) — (18.2,-20.3); \fill [black] (18.2,-20.3) — (17.4,-19.8) — (17.4,-20.8); \draw (15.15,-20.8) node [below] {$0,1$}; \draw [black] (24.2,-20.3) — (29.5,-20.3); \fill [black] (29.5,-20.3) — (28.7,-19.8) — (28.7,-20.8); \draw (26.85,-20.8) node [below] {$0,1$}; \draw [black] (4.1,-20.3) — (6.1,-20.3); \fill [black] (6.1,-20.3) — (5.3,-19.8) — (5.3,-20.8); \draw [black] (47,-20.3) — (52.3,-20.3); \fill [black] (52.3,-20.3) — (51.5,-19.8) — (51.5,-20.8); \draw (49.65,-20.8) node [below] {$0,1$}; \draw [black] (58.109,-19.281) arc (137.65981:-150.34019:2.25); \draw (62.66,-21.15) node [right] {$0,1$}; \fill [black] (57.82,-21.91) — (58.07,-22.82) — (58.75,-22.08); \end{tikzpicture} \end{center} \item {[less than equals]} \begin{center} \begin{tikzpicture}[scale=0.2] \tikzstyle{every node}+=[inner sep=0pt] \draw [black] (9.1,-20.3) circle (3); \draw (9.1,-20.3) node {$1$}; \draw [black] (9.1,-20.3) circle (2.4); \draw [black] (21.2,-20.3) circle (3); \draw (21.2,-20.3) node {$2$}; \draw [black] (21.2,-20.3) circle (2.4); \draw [black] (32.5,-20.3) circle (3); \draw (32.5,-20.3) node {$....$}; \draw [black] (32.5,-20.3) circle (2.4); \draw [black] (44,-20.3) circle (3); \draw (44,-20.3) node {$n+1$}; \draw [black] (44,-20.3) circle (2.4); \draw [black] (55.3,-20.3) circle (3); \draw (55.3,-20.3) node {$D$}; \draw [black] (35.5,-20.3) — (41,-20.3); \fill [black] (41,-20.3) — (40.2,-19.8) — (40.2,-20.8); \draw (38.25,-20.8) node [below] {$0,1$}; \draw [black] (12.1,-20.3) — (18.2,-20.3); \fill [black] (18.2,-20.3) — (17.4,-19.8) — (17.4,-20.8); \draw (15.15,-20.8) node [below] {$0,1$}; \draw [black] (24.2,-20.3) — (29.5,-20.3); \fill [black] (29.5,-20.3) — (28.7,-19.8) — (28.7,-20.8); \draw (26.85,-20.8) node [below] {$0,1$}; \draw [black] (4.1,-20.3) — (6.1,-20.3); \fill [black] (6.1,-20.3) — (5.3,-19.8) — (5.3,-20.8); \draw [black] (47,-20.3) — (52.3,-20.3); \fill [black] (52.3,-20.3) — (51.5,-19.8) — (51.5,-20.8); \draw (49.65,-20.8) node [below] {$0,1$}; \draw [black] (58.109,-19.281) arc (137.65981:-150.34019:2.25); \draw (62.66,-21.15) node [right] {$0,1$}; \fill [black] (57.82,-21.91) — (58.07,-22.82) — (58.75,-22.08); \end{tikzpicture} \end{center} \end{enumerate} {[\bfseries Symbol Count:]}\par \begin{enumerate} \item {[mod counter]} \begin{center} \begin{tikzpicture}[scale=0.2] \tikzstyle{every node}+=[inner sep=0pt] \draw [black] (9.7,-20.3) circle (3); \draw (9.7,-20.3) node {$1$}; \draw [black] (9.7,-20.3) circle (2.4); \draw [black] (21.4,-20.3) circle (3); \draw (21.4,-20.3) node {$2$}; \draw [black] (32.5,-20.3) circle (3); \draw (32.5,-20.3) node {$....$}; \draw [black] (44,-20.3) circle (3); \draw (44,-20.3) node {$n$}; \draw [black] (35.5,-20.3) — (41,-20.3); \fill [black] (41,-20.3) — (40.2,-19.8) — (40.2,-20.8); \draw (38.25,-20.8) node [below] {$0$}; \draw [black] (24.4,-20.3) — (29.5,-20.3); \fill [black] (29.5,-20.3) — (28.7,-19.8) — (28.7,-20.8); \draw (26.95,-20.8) node [below] {$0$}; \draw [black] (4.7,-20.3) — (6.7,-20.3); \fill [black] (6.7,-20.3) — (5.9,-19.8) — (5.9,-20.8); \draw [black] (42.213,-22.707) arc (-40.82091:-139.17909:20.302); \fill [black] (11.49,-22.71) — (11.63,-23.64) — (12.39,-22.99); \draw (26.85,-30.24) node [below] {$0$}; \draw [black] (12.7,-20.3) — (18.4,-20.3); \fill [black] (18.4,-20.3) — (17.6,-19.8) — (17.6,-20.8); \draw (15.55,-20.8) node [below] {$0$}; \draw [black] (8.377,-17.62) arc (234:-54:2.25); \draw (9.7,-13.05) node [above] {$1$}; \fill [black] (11.02,-17.62) — (11.9,-17.27) — (11.09,-16.68); \draw [black] (20.077,-17.62) arc (234:-54:2.25); \draw (21.4,-13.05) node [above] {$1$}; \fill [black] (22.72,-17.62) — (23.6,-17.27) — (22.79,-16.68); \draw [black] (31.177,-17.62) arc (234:-54:2.25); \draw (32.5,-13.05) node [above] {$1$}; \fill [black] (33.82,-17.62) — (34.7,-17.27) — (33.89,-16.68); \draw [black] (42.677,-17.62) arc (234:-54:2.25); \draw (44,-13.05) node [above] {$1$}; \fill [black] (45.32,-17.62) — (46.2,-17.27) — (45.39,-16.68); \end{tikzpicture} \end{center} \item {[cross counter]} \begin{center} \begin{tikzpicture}[scale=0.2] \tikzstyle{every node}+=[inner sep=0pt] \draw [black] (6.6,-18.4) circle (3); \draw (6.6,-18.4) node {$1$}; \draw [black] (6.6,-18.4) circle (2.4); \draw [black] (22.3,-18.4) circle (3); \draw (22.3,-18.4) node {$...$}; \draw [black] (38,-18.4) circle (3); \draw (38,-18.4) node {$n$}; \draw [black] (6.6,-31.1) circle (3); \draw (6.6,-31.1) node {$...$}; \draw [black] (22.3,-31.1) circle (3); \draw (22.3,-31.1) node {$...$}; \draw [black] (38,-31.1) circle (3); \draw (38,-31.1) node {$n$}; \draw [black] (6.6,-44.4) circle (3); \draw (6.6,-44.4) node {$m$}; \draw [black] (22.3,-44.4) circle (3); \draw (22.3,-44.4) node {$m$}; \draw [black] (38,-44.4) circle (3); \draw (38,-44.4) node {$m/n$}; \draw [black] (2.8,-14.5) — (4.51,-16.25); \fill [black] (4.51,-16.25) — (4.31,-15.33) — (3.59,-16.03); \draw [black] (9.003,-16.608) arc (123.17377:56.82623:24.3); \fill [black] (9,-16.61) — (9.95,-16.59) — (9.4,-15.75); \draw (22.3,-12.15) node [above] {$0$}; \draw [black] (9.6,-18.4) — (19.3,-18.4); \fill [black] (19.3,-18.4) — (18.5,-17.9) — (18.5,-18.9); \draw (14.45,-18.9) node [below] {$0$}; \draw [black] (25.3,-18.4) — (35,-18.4); \fill [black] (35,-18.4) — (34.2,-17.9) — (34.2,-18.9); \draw (30.15,-18.9) node [below] {$0$}; \draw [black] (6.6,-21.4) — (6.6,-28.1); \fill [black] (6.6,-28.1) — (7.1,-27.3) — (6.1,-27.3); \draw (7.1,-24.75) node [right] {$1$}; \draw [black] (22.3,-21.4) — (22.3,-28.1); \fill [black] (22.3,-28.1) — (22.8,-27.3) — (21.8,-27.3); \draw (22.8,-24.75) node [right] {$1$}; \draw [black] (38,-21.4) — (38,-28.1); \fill [black] (38,-28.1) — (38.5,-27.3) — (37.5,-27.3); \draw (38.5,-24.75) node [right] {$1$}; \draw [black] (6.6,-34.1) — (6.6,-41.4); \fill [black] (6.6,-41.4) — (7.1,-40.6) — (6.1,-40.6); \draw (7.1,-37.75) node [right] {$1$}; \draw [black] (22.3,-34.1) — (22.3,-41.4); \fill [black] (22.3,-41.4) — (22.8,-40.6) — (21.8,-40.6); \draw (22.8,-37.75) node [right] {$1$}; \draw [black] (38,-34.1) — (38,-41.4); \fill [black] (38,-41.4) — (38.5,-40.6) — (37.5,-40.6); \draw (38.5,-37.75) node [right] {$1$}; \draw [black] (4.686,-42.094) arc (-144.91381:-215.08619:18.605); \fill [black] (4.69,-20.71) — (3.82,-21.07) — (4.63,-21.65); \draw (0.8,-31.4) node [left] {$1$}; \draw [black] (20.412,-42.073) arc (-145.50571:-214.49429:18.846); \fill [black] (20.41,-20.73) — (19.55,-21.1) — (20.37,-21.67); \draw (16.6,-31.4) node [left] {$1$}; \draw [black] (36.212,-41.994) arc (-147.71492:-212.28508:19.835); \fill [black] (36.21,-20.81) — (35.36,-21.21) — (36.21,-21.75); \draw (32.65,-31.4) node [left] {$1$}; \draw [black] (19.711,-32.603) arc (-66.39845:-113.60155:13.141); \fill [black] (19.71,-32.6) — (18.78,-32.47) — (19.18,-33.38); \draw (14.45,-34.2) node [below] {$0$}; \draw [black] (35.382,-32.552) arc (-67.32639:-112.67361:13.572); \fill [black] (35.38,-32.55) — (34.45,-32.4) — (34.84,-33.32); \draw (30.15,-34.1) node [below] {$0$}; \draw [black] (9.6,-44.4) — (19.3,-44.4); \fill [black] (19.3,-44.4) — (18.5,-43.9) — (18.5,-44.9); \draw (14.45,-44.9) node [below] {$0$}; \draw [black] (25.3,-44.4) — (35,-44.4); \fill [black] (35,-44.4) — (34.2,-43.9) — (34.2,-44.9); \draw (30.15,-44.9) node [below] {$0$}; \draw [black] (35.573,-46.16) arc (-57.52516:-122.47484:24.72); \fill [black] (9.03,-46.16) — (9.43,-47.01) — (9.97,-46.17); \draw (22.3,-50.53) node [below] {$0$}; \end{tikzpicture} \end{center} \end{enumerate} {[\bfseries Particular Substring]}\par \begin{enumerate} \item {[starting with]} \begin{center} \begin{tikzpicture}[scale=0.2] \tikzstyle{every node}+=[inner sep=0pt] \draw [black] (8.5,-18.4) circle (3); \draw (8.5,-18.4) node {$1$}; \draw [black] (23,-18.4) circle (3); \draw (23,-18.4) node {$...$}; \draw [black] (37.3,-18.4) circle (3); \draw (37.3,-18.4) node {$...$}; \draw [black] (49.8,-18.4) circle (3); \draw (49.8,-18.4) node {$n+1$}; \draw [black] (49.8,-18.4) circle (2.4); \draw [black] (37.3,-34.5) circle (3); \draw (37.3,-34.5) node {$D$}; \draw [black] (3.8,-18.4) — (5.5,-18.4); \fill [black] (5.5,-18.4) — (4.7,-17.9) — (4.7,-18.9); \draw [black] (11.5,-18.4) — (20,-18.4); \fill [black] (20,-18.4) — (19.2,-17.9) — (19.2,-18.9); \draw (15.75,-17.9) node [above] {$x1$}; \draw [black] (26,-18.4) — (34.3,-18.4); \fill [black] (34.3,-18.4) — (33.5,-17.9) — (33.5,-18.9); \draw (30.15,-17.9) node [above] {$x..$}; \draw [black] (40.3,-18.4) — (46.8,-18.4); \fill [black] (46.8,-18.4) — (46,-17.9) — (46,-18.9); \draw (43.55,-17.9) node [above] {$xn$}; \draw [black] (11.12,-19.86) — (34.68,-33.04); \fill [black] (34.68,-33.04) — (34.23,-32.21) — (33.74,-33.08); \draw (24.58,-25.95) node [above] {$x{1}^{\prime }$}; \draw [black] (24.99,-20.64) — (35.31,-32.26); \fill [black] (35.31,-32.26) — (35.15,-31.33) — (34.4,-31.99); \draw (30.69,-25) node [right] {$x.{.}^{\prime }$}; \draw [black] (37.3,-21.4) — (37.3,-31.5); \fill [black] (37.3,-31.5) — (37.8,-30.7) — (36.8,-30.7); \draw (37.8,-26.45) node [right] {$x{n}^{\prime }$}; \draw [black] (48.477,-15.72) arc (234:-54:2.25); \draw (49.8,-11.15) node [above] {$0,1$}; \fill [black] (51.12,-15.72) — (52,-15.37) — (51.19,-14.78); \draw [black] (38.623,-37.18) arc (54:-234:2.25); \draw (37.3,-41.75) node [below] {$0,1$}; \fill [black] (35.98,-37.18) — (35.1,-37.53) — (35.91,-38.12); \end{tikzpicture} \end{center} \item {[containing]} \begin{center} \begin{tikzpicture}[scale=0.2] \tikzstyle{every node}+=[inner sep=0pt] \draw [black] (9.6,-18.4) circle (3); \draw (9.6,-18.4) node {$1$}; \draw [black] (23.7,-18.4) circle (3); \draw (23.7,-18.4) node {$...$}; \draw [black] (37.3,-18.4) circle (3); \draw (37.3,-18.4) node {$...$}; \draw [black] (49.8,-18.4) circle (3); \draw (49.8,-18.4) node {$n+1$}; \draw [black] (49.8,-18.4) circle (2.4); \draw [black] (4.9,-18.4) — (6.6,-18.4); \fill [black] (6.6,-18.4) — (5.8,-17.9) — (5.8,-18.9); \draw [black] (12.6,-18.4) — (20.7,-18.4); \fill [black] (20.7,-18.4) — (19.9,-17.9) — (19.9,-18.9); \draw (16.65,-17.9) node [above] {$x1$}; \draw [black] (26.7,-18.4) — (34.3,-18.4); \fill [black] (34.3,-18.4) — (33.5,-17.9) — (33.5,-18.9); \draw (30.5,-17.9) node [above] {$x..$}; \draw [black] (40.3,-18.4) — (46.8,-18.4); \fill [black] (46.8,-18.4) — (46,-17.9) — (46,-18.9); \draw (43.55,-17.9) node [above] {$xn$}; \draw [black] (48.477,-15.72) arc (234:-54:2.25); \draw (49.8,-11.15) node [above] {$0,1$}; \fill [black] (51.12,-15.72) — (52,-15.37) — (51.19,-14.78); \draw [black] (8.277,-15.72) arc (234:-54:2.25); \draw (9.6,-11.15) node [above] {$x{1}^{\prime }$}; \fill [black] (10.92,-15.72) — (11.8,-15.37) — (10.99,-14.78); \draw [black] (22.246,-21.001) arc (-40.82419:-139.17581:7.395); \fill [black] (11.05,-21) — (11.2,-21.93) — (11.96,-21.28); \draw (16.65,-24.06) node [below] {$x.{.}^{\prime }[✓]$}; \draw [black] (36.837,-21.358) arc (-15.09784:-164.90216:13.865); \fill [black] (10.06,-21.36) — (9.79,-22.26) — (10.75,-22); \draw (23.45,-32.11) node [below] {$x{n}^{\prime }[✓]$}; \end{tikzpicture} \end{center} \item {[ending with]} \begin{center} \begin{tikzpicture}[scale=0.2] \tikzstyle{every node}+=[inner sep=0pt] \draw [black] (8.5,-18.4) circle (3); \draw (8.5,-18.4) node {$1$}; \draw [black] (23,-18.4) circle (3); \draw (23,-18.4) node {$...$}; \draw [black] (37.3,-18.4) circle (3); \draw (37.3,-18.4) node {$...$}; \draw [black] (49.8,-18.4) circle (3); \draw (49.8,-18.4) node {$n+1$}; \draw [black] (49.8,-18.4) circle (2.4); \draw [black] (3.8,-18.4) — (5.5,-18.4); \fill [black] (5.5,-18.4) — (4.7,-17.9) — (4.7,-18.9); \draw [black] (11.5,-18.4) — (20,-18.4); \fill [black] (20,-18.4) — (19.2,-17.9) — (19.2,-18.9); \draw (15.75,-17.9) node [above] {$x1$}; \draw [black] (26,-18.4) — (34.3,-18.4); \fill [black] (34.3,-18.4) — (33.5,-17.9) — (33.5,-18.9); \draw (30.15,-17.9) node [above] {$x..$}; \draw [black] (40.3,-18.4) — (46.8,-18.4); \fill [black] (46.8,-18.4) — (46,-17.9) — (46,-18.9); \draw (43.55,-17.9) node [above] {$xn$}; \draw [black] (49.131,-21.322) arc (-17.01416:-162.98584:20.895); \fill [black] (9.17,-21.32) — (8.93,-22.23) — (9.88,-21.94); \draw (29.15,-36.6) node [below] {$0,1[✓]$}; \draw [black] (7.177,-15.72) arc (234:-54:2.25); \draw (8.5,-11.15) node [above] {$x{1}^{\prime }$}; \fill [black] (9.82,-15.72) — (10.7,-15.37) — (9.89,-14.78); \draw [black] (20.68,-20.283) arc (-59.72477:-120.27523:9.778); \fill [black] (10.82,-20.28) — (11.26,-21.12) — (11.76,-20.25); \draw (15.75,-22.12) node [below] {$x.{.}^{\prime }[✓]$}; \draw [black] (35.743,-20.959) arc (-36.67819:-143.32181:16.014); \fill [black] (10.06,-20.96) — (10.13,-21.9) — (10.94,-21.3); \draw (22.9,-27.91) node [below] {$x{n}^{\prime }[✓]$}; \end{tikzpicture} \end{center} \end{enumerate} \subsection{Minimization Of DFAs} \begin{enumerate} \item ~[Remove the unreachable states]\par \begin{center} \begin{tikzpicture}[scale=0.2] \tikzstyle{every node}+=[inner sep=0pt] \draw [black] (23.8,-18.4) circle (3); \draw (23.8,-18.4) node {$...$}; \draw [black] (39.8,-18.4) circle (3); \draw (39.8,-18.4) node {$...$}; \draw [black] (14.6,-24.4) circle (3); \draw (14.6,-24.4) node {$x$}; \draw [black] (48.8,-24.4) circle (3); \draw (48.8,-24.4) node {$x$}; \draw [black] (19.1,-18.4) — (20.8,-18.4); \fill [black] (20.8,-18.4) — (20,-17.9) — (20,-18.9); \draw [black] (25.499,-15.945) arc (135.5707:44.4293:8.823); \fill [black] (38.1,-15.95) — (37.9,-15.02) — (37.18,-15.72); \draw (31.8,-12.8) node [above] {$0,1$}; \draw [black] (38.158,-20.893) arc (-43.21493:-136.78507:8.724); \fill [black] (25.44,-20.89) — (25.63,-21.82) — (26.35,-21.13); \draw (31.8,-24.14) node [below] {$0,1$}; \draw [black] (46.3,-22.74) — (42.3,-20.06); \fill [black] (42.3,-20.06) — (42.68,-20.92) — (43.24,-20.09); \draw (43.3,-21.9) node [below] {$x$}; \draw [black] (17.11,-22.76) — (21.29,-20.04); \fill [black] (21.29,-20.04) — (20.34,-20.06) — (20.89,-20.89); \draw (20.2,-21.9) node [below] {$x$}; \end{tikzpicture} \end{center} \item [Merge the unrecognizable states with terminals in contact] \begin{table}[H] \def\arraystretch{1.3} \centering ~~~~~~~~~~\begin{tabular}{|p{1cm}|p{1cm}|p{1cm}|} \hline $K^{\prime }s$ & $\Delta 0$ & $\Delta 1$\\hline $\to s$ & $q_1$ & $...$\\hline $q_1$ & $...$ & $\ast F$\\hline \end{tabular} \end{table} \begin{table}[H] \def\arraystretch{1.3} \centering ~~~~~~~~~~\begin{tabular}{|p{3cm}|p{5cm}|} \hline Equivalency & Classes\\hline 0 & [$s,q_1,q_2,\dots$][$F^{\prime }s$]\\hline 1 & $[q^{\prime }s{⊢}_M[\ast ]]\dots [f^{\prime }s{⊢}_M[\ast ]]$\\hline … & …\\hline \end{tabular} \end{table} \end{enumerate} \subsection{Non RLs} [“sufficiently long strings in RLs may be pumped- that is have a middle section of the string repeated an arbitrary number of times- to produce a new word that also lies within the language thus exists a constant $p$ such that any string $w$ in $L$ with length at least $p$ can be split into three substrings $w=xyz$ where middle portion $y$ must not be empty, such that the words constructed by repeating $y$ zero or more times are still in $L$, moreover, guarantees that the length of $xy$ will be at most $p$, imposing a limit on the ways $w$ may be split”] $[Ex:0^n{1}^n,\to 0^p{1}^p:|xy|\le p\to y=0^x]$ \section{Nondeterminism} {\bfseries [Informal:]}\par [A NFA allows multiple transition for same set of inputs thereby clones itself into appropriately many copies, each following a different transition; if no transition is available, the copy dies meanwhile; if any of the clone ends up in final state, the input is said to be accepted] \par{\bfseries[Formal:]} \par [a NFA is $M=(K,\Sigma ,\Delta ,s,F)$ where $\Delta$ is the transition relation is a subset of $K\times (\Sigma \cup \{e\})\times K$] \begin{table}[H] \def\arraystretch{1.3} \centering ~~~~~~~~~~\begin{tabular}{|p{2.5cm}|p{2cm}|p{2cm}|} \hline $K^{\prime }s$ & ${ϵ}^{\ast }\Delta 0{ϵ}^{\ast }$ & ${ϵ}^{\ast }\Delta 1{ϵ}^{\ast }$\\hline $\to s$ & $\{q_1,\dots \}$ & $...$\\hline $q_1$ & $...$ & $...$\\hline $...$ & $...$ & $\ast F(\to ϵ)$\\hline \end{tabular} \end{table} \begin{table}[H] \def\arraystretch{1.3} \centering ~~~~~~~~~~\begin{tabular}{|p{2.5cm}|p{2cm}|p{2cm}|} \hline $K^{\prime }s$ & $\Delta 0$ & $\Delta 1$\\hline $\to s$ & $\{q_1,\dots \}$ & $...$\\hline $[q_1,\dots ]$ & $...\cup ...$ & $...\cup ...$\\hline Reachables & $...$ & $...$\\hline \end{tabular} \end{table} \section{Regular Expressions} [compact generative description of a RL through symbols, possibly with aid of parenthesis recursively] \begin{enumerate} \item {[Empty and Singleton: $L(0\in \Sigma )=\{0\},L(ϵ)=\{ϵ\},L(\varnothing )=\{\}$]} \begin{center} \begin{tikzpicture}[scale=0.2] \tikzstyle{every node}+=[inner sep=0pt] \draw [black] (21.7,-11.1) circle (3); \draw (21.7,-11.1) node {$qf$}; \draw [black] (21.7,-11.1) circle (2.4); \draw [black] (34.6,-11.1) circle (3); \draw (34.6,-11.1) node {$s$}; \draw [black] (46.3,-11.1) circle (3); \draw (46.3,-11.1) node {$qf$}; \draw [black] (46.3,-11.1) circle (2.4); \draw [black] (59.2,-11.1) circle (3); \draw (59.2,-11.1) node {$s$}; \draw [black] (10.1,-11.1) circle (3); \draw (10.1,-11.1) node {$s$}; \draw [black] (70.9,-11.1) circle (3); \draw (70.9,-11.1) node {$qf$}; \draw [black] (70.9,-11.1) circle (2.4); \draw [black] (13.1,-11.1) — (18.7,-11.1); \fill [black] (18.7,-11.1) — (17.9,-10.6) — (17.9,-11.6); \draw (15.9,-10.6) node [above] {$0$}; \draw [black] (5.8,-11.1) — (7.1,-11.1); \fill [black] (7.1,-11.1) — (6.3,-10.6) — (6.3,-11.6); \draw [black] (37.6,-11.1) — (43.3,-11.1); \fill [black] (43.3,-11.1) — (42.5,-10.6) — (42.5,-11.6); \draw (40.45,-10.6) node [above] {$ϵ$}; \draw [black] (30.3,-11.1) — (31.6,-11.1); \fill [black] (31.6,-11.1) — (30.8,-10.6) — (30.8,-11.6); \draw [black] (54.9,-11.1) — (56.2,-11.1); \fill [black] (56.2,-11.1) — (55.4,-10.6) — (55.4,-11.6); \end{tikzpicture} \end{center} \item {[Operands: $L(RS)=L(R)\circ L(S),L(R\cup S)=L(R)\cup L(S),L(R^{\ast })=L(R{)}^{\ast }$]}

\begin{center} \begin{tikzpicture}[scale=0.2] \tikzstyle{every node}+=[inner sep=0pt] \draw [black] (21.7,-11.1) circle (3); \draw (21.7,-11.1) node {$...$}; \draw [black] (34.6,-11.1) circle (3); \draw (34.6,-11.1) node {$...$}; \draw [black] (46.3,-11.1) circle (3); \draw (46.3,-11.1) node {$...$}; \draw [black] (59.2,-11.1) circle (3); \draw (59.2,-11.1) node {$...$}; \draw [black] (10.1,-11.1) circle (3); \draw (10.1,-11.1) node {$s$}; \draw [black] (70.9,-11.1) circle (3); \draw (70.9,-11.1) node {$qf$}; \draw [black] (70.9,-11.1) circle (2.4); \draw [black] (34.6,-19.6) circle (3); \draw (34.6,-19.6) node {$...$}; \draw [black] (46.3,-19.6) circle (3); \draw (46.3,-19.6) node {$...$}; \draw [black] (59.2,-23.7) circle (3); \draw (59.2,-23.7) node {$qf$}; \draw [black] (59.2,-23.7) circle (2.4); \draw [black] (34.6,-28.2) circle (3); \draw (34.6,-28.2) node {$...$}; \draw [black] (46.3,-28.2) circle (3); \draw (46.3,-28.2) node {$...$}; \draw [black] (21.7,-23.7) circle (3); \draw (21.7,-23.7) node {$s$}; \draw [black] (34.6,-39) circle (3); \draw (34.6,-39) node {$...$}; \draw [black] (46.3,-39) circle (3); \draw (46.3,-39) node {$...$}; \draw [black] (21.7,-39) circle (3); \draw (21.7,-39) node {$s$}; \draw [black] (59.2,-39) circle (3); \draw (59.2,-39) node {$qf$}; \draw [black] (59.2,-39) circle (2.4); \draw [black] (24.7,-11.1) — (31.6,-11.1); \fill [black] (31.6,-11.1) — (30.8,-10.6) — (30.8,-11.6); \draw (28.15,-10.6) node [above] {$...R...$}; \draw [black] (49.3,-11.1) — (56.2,-11.1); \fill [black] (56.2,-11.1) — (55.4,-10.6) — (55.4,-11.6); \draw (52.75,-10.6) node [above] {$...S...$}; \draw [black] (13.1,-11.1) — (18.7,-11.1); \fill [black] (18.7,-11.1) — (17.9,-10.6) — (17.9,-11.6); \draw (15.9,-10.6) node [above] {$ϵ$}; \draw [black] (62.2,-11.1) — (67.9,-11.1); \fill [black] (67.9,-11.1) — (67.1,-10.6) — (67.1,-11.6); \draw (65.05,-10.6) node [above] {$ϵ$}; \draw [black] (5.8,-11.1) — (7.1,-11.1); \fill [black] (7.1,-11.1) — (6.3,-10.6) — (6.3,-11.6); \draw [black] (31.6,-11.1) — (24.7,-11.1); \fill [black] (24.7,-11.1) — (25.5,-11.6) — (25.5,-10.6); \draw [black] (56.2,-11.1) — (49.3,-11.1); \fill [black] (49.3,-11.1) — (50.1,-11.6) — (50.1,-10.6); \draw [black] (37.6,-11.1) — (43.3,-11.1); \fill [black] (43.3,-11.1) — (42.5,-10.6) — (42.5,-11.6); \draw (40.45,-10.6) node [above] {$ϵ$}; \draw [black] (17.5,-23.7) — (18.7,-23.7); \fill [black] (18.7,-23.7) — (17.9,-23.2) — (17.9,-24.2); \draw [black] (24.56,-22.79) — (31.74,-20.51); \fill [black] (31.74,-20.51) — (30.83,-20.27) — (31.13,-21.23); \draw (27.35,-21.11) node [above] {$ϵ$}; \draw [black] (24.53,-24.69) — (31.77,-27.21); \fill [black] (31.77,-27.21) — (31.18,-26.48) — (30.85,-27.42); \draw (27.31,-26.48) node [below] {$ϵ$}; \draw [black] (37.6,-19.6) — (43.3,-19.6); \fill [black] (43.3,-19.6) — (42.5,-19.1) — (42.5,-20.1); \draw (40.45,-19.1) node [above] {$...R...$}; \draw [black] (43.3,-19.6) — (37.6,-19.6); \fill [black] (37.6,-19.6) — (38.4,-20.1) — (38.4,-19.1); \draw [black] (37.6,-28.2) — (43.3,-28.2); \fill [black] (43.3,-28.2) — (42.5,-27.7) — (42.5,-28.7); \draw (40.45,-27.7) node [above] {$...S...$}; \draw [black] (43.3,-28.2) — (37.6,-28.2); \fill [black] (37.6,-28.2) — (38.4,-28.7) — (38.4,-27.7); \draw [black] (49.13,-27.21) — (56.37,-24.69); \fill [black] (56.37,-24.69) — (55.45,-24.48) — (55.78,-25.42); \draw (53.59,-26.48) node [below] {$ϵ$}; \draw [black] (49.16,-20.51) — (56.34,-22.79); \fill [black] (56.34,-22.79) — (55.73,-22.07) — (55.43,-23.03); \draw (53.55,-21.11) node [above] {$ϵ$}; \draw [black] (37.6,-39) — (43.3,-39); \fill [black] (43.3,-39) — (42.5,-38.5) — (42.5,-39.5); \draw (40.45,-38.5) node [above] {$...R...$}; \draw [black] (45.899,-41.94) arc (-22.35921:-157.64079:5.892); \fill [black] (35,-41.94) — (34.84,-42.87) — (35.77,-42.49); \draw (40.45,-46.09) node [below] {$ϵ$}; \draw [black] (24.7,-39) — (31.6,-39); \fill [black] (31.6,-39) — (30.8,-38.5) — (30.8,-39.5); \draw (28.15,-38.5) node [above] {$ϵ$}; \draw [black] (49.3,-39) — (56.2,-39); \fill [black] (56.2,-39) — (55.4,-38.5) — (55.4,-39.5); \draw (52.75,-38.5) node [above] {$ϵ$}; \draw [black] (17.5,-39) — (18.7,-39); \fill [black] (18.7,-39) — (17.9,-38.5) — (17.9,-39.5); \draw [black] (24.25,-37.421) arc (119.18334:60.81666:33.224); \fill [black] (56.65,-37.42) — (56.2,-36.59) — (55.71,-37.47); \draw (40.45,-32.7) node [above] {$ϵ$}; \draw [black] (43.3,-39) — (37.6,-39); \fill [black] (37.6,-39) — (38.4,-39.5) — (38.4,-38.5); \end{tikzpicture} \end{center}\par Eg: \begin{center} \begin{tikzpicture}[scale=0.2] \tikzstyle{every node}+=[inner sep=0pt] \draw [black] (15.4,-13.9) circle (3); \draw (15.4,-13.9) node {$s$}; \draw [black] (25,-13.9) circle (3); \draw (25,-13.9) node {$q1$}; \draw [black] (34.6,-13.9) circle (3); \draw (34.6,-13.9) node {$qf$}; \draw [black] (34.6,-13.9) circle (2.4); \draw [black] (44,-13.9) circle (3); \draw (44,-13.9) node {$s$}; \draw [black] (54.8,-13.9) circle (3); \draw (54.8,-13.9) node {$qf$}; \draw [black] (54.8,-13.9) circle (2.4); \draw [black] (64.3,-13.9) circle (3); \draw (64.3,-13.9) node {$qf$}; \draw [black] (64.3,-13.9) circle (2.4); \draw [black] (11.1,-13.9) — (12.4,-13.9); \fill [black] (12.4,-13.9) — (11.6,-13.4) — (11.6,-14.4); \draw [black] (18.4,-13.9) — (22,-13.9); \fill [black] (22,-13.9) — (21.2,-13.4) — (21.2,-14.4); \draw (20.2,-13.4) node [above] {$0$}; \draw [black] (28,-13.9) — (31.6,-13.9); \fill [black] (31.6,-13.9) — (30.8,-13.4) — (30.8,-14.4); \draw (29.8,-13.4) node [above] {$1$}; \draw [black] (47,-13.9) — (51.8,-13.9); \fill [black] (51.8,-13.9) — (51,-13.4) — (51,-14.4); \draw (49.4,-13.4) node [above] {$0,1$}; \draw [black] (39.7,-13.9) — (41,-13.9); \fill [black] (41,-13.9) — (40.2,-13.4) — (40.2,-14.4); \draw [black] (60,-13.9) — (61.3,-13.9); \fill [black] (61.3,-13.9) — (60.5,-13.4) — (60.5,-14.4); \draw [black] (65.407,-11.124) arc (185.98721:-102.01279:2.25); \draw (69.86,-7.93) node [right] {$0$}; \fill [black] (67.18,-13.09) — (68.02,-13.5) — (67.92,-12.51); \end{tikzpicture} \end{center}

\end{enumerate} {\bfseries [NFA to RegEx]} \par[remove intermediate middle states successively keeping each incoming paths through consistent] \begin{enumerate} \item {[non-transitioning exclusive terminal states]} \item {[update transitions accordingly for each non terminal eliminations]} \end{enumerate} {\bfseries [RegEx to NFA]} \par[peel regex off recursively into constituent atoms successively developing each steps into nfas] \begin{enumerate} \item {[greatest precendences]} \item {[construct a portion of nfas for each shortens possibly with overlaps]} \end{enumerate} \section{Context Free Grammar} {\bfseries [Informal:]}\par [complex generators root on the complete understanding of the structures involves recursive rules] $[\text{variables}:\text{strings ∪ variables}]$ {[\bfseries Formal:]} \par [a CFG $G$ is a quadruple $(V,\Sigma ,R,S)$ where] \begin{enumerate} \item {[V is an alphabet]} \item {[$\Sigma$, the set of terminals is a subset of $V$]} \item {[$R$, the set of rules is a finite subset of $(V-\Sigma )\times V^{\ast }$]} \item {[$S$, the start symbol is an element of $V-\Sigma$]} \end{enumerate} [a string $w\in L(G)$ if and only if $S{\to }_G^{\ast }w$ where ${\to }_G^{\ast }$ is rt closure of the one step ${\to }_G$ generation] \subsection{CFG Construction} {[\bfseries General Tips:]}\par \begin{enumerate} \item {[Think inside out as that’s the way CFG work for symmetry]} \item {[You always need to look for the mirror images]} $[Eg:0^n{1}^n,n>0:S\to 0S1|01]$ \end{enumerate} {[\bfseries From RegEx:]} $[0:S\to 0;r+s:S\to r|s;rs:S\to rA,A\to s;r^{\ast }:S\to rS|ϵ]$ \subsection{Parse Trees} [a pictorial entity for structures of derivation of a particular string from some non-terminal variables] $[\text{a parse tree}=[\text{leftmost derivation, …, rightmost derivation}]]$ [certain CFGs derive a string with multiple trees, such are still valid but with ambiguous meanings] $[Eg:S\to S\ast S|S+S|id]$ \begin{center} \begin{tikzpicture}[scale=0.12] \tikzstyle{every node}+=[inner sep=0pt] \draw [black] (23.8,-12.2) circle (3); \draw (23.8,-12.2) node {$S$}; \draw [black] (23.8,-20.3) circle (3); \draw (23.8,-20.3) node {$\ast$}; \draw [black] (23.8,-20.3) circle (2.4); \draw [black] (16.2,-20.3) circle (3); \draw (16.2,-20.3) node {$S$}; \draw [black] (31.5,-20.3) circle (3); \draw (31.5,-20.3) node {$S$}; \draw [black] (8.3,-28) circle (3); \draw (8.3,-28) node {$S$}; \draw [black] (23.8,-28) circle (3); \draw (23.8,-28) node {$S$}; \draw [black] (16.2,-28) circle (3); \draw (16.2,-28) node {$+$}; \draw [black] (16.2,-28) circle (2.4); \draw [black] (31.5,-28) circle (3); \draw (31.5,-28) node {$id$}; \draw [black] (31.5,-28) circle (2.4); \draw [black] (8.3,-35.5) circle (3); \draw (8.3,-35.5) node {$id$}; \draw [black] (8.3,-35.5) circle (2.4); \draw [black] (23.8,-35.5) circle (3); \draw (23.8,-35.5) node {$id$}; \draw [black] (23.8,-35.5) circle (2.4); \draw [black] (49,-12.2) circle (3); \draw (49,-12.2) node {$S$}; \draw [black] (49,-20.3) circle (3); \draw (49,-20.3) node {$+$}; \draw [black] (49,-20.3) circle (2.4); \draw [black] (41.6,-20.3) circle (3); \draw (41.6,-20.3) node {$S$}; \draw [black] (56.5,-20.3) circle (3); \draw (56.5,-20.3) node {$S$}; \draw [black] (49,-28) circle (3); \draw (49,-28) node {$S$}; \draw [black] (49,-35.5) circle (3); \draw (49,-35.5) node {$id$}; \draw [black] (49,-35.5) circle (2.4); \draw [black] (41.6,-28) circle (3); \draw (41.6,-28) node {$id$}; \draw [black] (41.6,-28) circle (2.4); \draw [black] (56.5,-28) circle (3); \draw (56.5,-28) node {$\ast$}; \draw [black] (56.5,-28) circle (2.4); \draw [black] (64.4,-28) circle (3); \draw (64.4,-28) node {$S$}; \draw [black] (64.4,-35.5) circle (3); \draw (64.4,-35.5) node {$id$}; \draw [black] (64.4,-35.5) circle (2.4); \draw [black] (23.8,-15.2) — (23.8,-17.3); \fill [black] (23.8,-17.3) — (24.3,-16.5) — (23.3,-16.5); \draw [black] (21.75,-14.39) — (18.25,-18.11); \fill [black] (18.25,-18.11) — (19.16,-17.87) — (18.44,-17.19); \draw [black] (25.87,-14.37) — (29.43,-18.13); \fill [black] (29.43,-18.13) — (29.24,-17.2) — (28.52,-17.89); \draw [black] (16.2,-23.3) — (16.2,-25); \fill [black] (16.2,-25) — (16.7,-24.2) — (15.7,-24.2); \draw [black] (18.31,-22.44) — (21.69,-25.86); \fill [black] (21.69,-25.86) — (21.49,-24.94) — (20.77,-25.65); \draw [black] (14.05,-22.39) — (10.45,-25.91); \fill [black] (10.45,-25.91) — (11.37,-25.71) — (10.67,-24.99); \draw [black] (31.5,-23.3) — (31.5,-25); \fill [black] (31.5,-25) — (32,-24.2) — (31,-24.2); \draw [black] (8.3,-31) — (8.3,-32.5); \fill [black] (8.3,-32.5) — (8.8,-31.7) — (7.8,-31.7); \draw [black] (23.8,-31) — (23.8,-32.5); \fill [black] (23.8,-32.5) — (24.3,-31.7) — (23.3,-31.7); \draw [black] (46.98,-14.41) — (43.62,-18.09); \fill [black] (43.62,-18.09) — (44.53,-17.83) — (43.79,-17.16); \draw [black] (49,-15.2) — (49,-17.3); \fill [black] (49,-17.3) — (49.5,-16.5) — (48.5,-16.5); \draw [black] (51.04,-14.4) — (54.46,-18.1); \fill [black] (54.46,-18.1) — (54.29,-17.17) — (53.55,-17.85); \draw [black] (49,-31) — (49,-32.5); \fill [black] (49,-32.5) — (49.5,-31.7) — (48.5,-31.7); \draw [black] (64.4,-31) — (64.4,-32.5); \fill [black] (64.4,-32.5) — (64.9,-31.7) — (63.9,-31.7); \draw [black] (58.65,-22.39) — (62.25,-25.91); \fill [black] (62.25,-25.91) — (62.03,-24.99) — (61.33,-25.71); \draw [black] (41.6,-23.3) — (41.6,-25); \fill [black] (41.6,-25) — (42.1,-24.2) — (41.1,-24.2); \draw [black] (56.5,-23.3) — (56.5,-25); \fill [black] (56.5,-25) — (57,-24.2) — (56,-24.2); \draw [black] (54.41,-22.45) — (51.09,-25.85); \fill [black] (51.09,-25.85) — (52.01,-25.63) — (51.29,-24.93); \end{tikzpicture} \end{center} \subsection{Normal Forms} [recognition devices for CFL demand modifications to grammar] \begin{enumerate} \item {[non recursive starters]} \item {[cleansing productions}] $[A\to ϵ,B\to xAx;A\to xAx;A\to B]$ \item {[normal forms]} $\text{[Chomsky A→BC or A→a], [Greibach A→ax]}$ \end{enumerate} \section{Pushdown Automata} {\bfseries [Informal:]}\par[accumulates inputs in succession thereafter checks them off]\par {[\bfseries Formal:]}\par [a PDA is a 7tuple $(K,\Sigma ,\Gamma ,s,F,Z,\Delta )$ where] \begin{enumerate} \item {[$K$ is a finite set of states]} \item {[$\Sigma$ is an alphabet of input symbols]} \item {[$\Gamma$ is an alphabet of stack symbols]} \item {[$s\in K$ is the initial state]} \item {[$F\subset K$ is the set of final states]} \item {[$Z\in \Gamma$ is the initial stack symbol]} \item {[$\Delta$ is the transition relation is a subset of $K\times (\Sigma \cup \{e\})\times \Gamma \times K\times {\Gamma }^{\ast }$]} \end{enumerate} [a string in $w\in {\Sigma }^{\ast }$ is said to be accepted if and only if there is a state $q\in F$ such that by following] \begin{enumerate} \item {[final state acceptance:]} $[(s,w,Z){⊢}_M^{\ast }(q,e,Z)]$ \item {[empty stack acceptance:]} $[(s,w,Z){⊢}_M^{\ast }(p,e,e)]$ \end{enumerate} [${⊢}_M^{\ast }$ is reflexive, transitive closure of the one move binary relation ${⊢}_M:K\times {\Sigma }^{+}\times {\Gamma }^{+}\to K\times {\Sigma }^{\ast }\times {\Gamma }^{\ast }$] \subsection{PDA Constructions} {[\bfseries General Tips:]} \begin{enumerate} \item {[Determine what information to push on the stack that can later be poped for comparison]} \item {[Establish a trigger move if pushing and poping are to be done successively]} $[\text{Eg: }{0}^n{1}^n,n>0]$ \begin{center} \begin{tikzpicture}[scale=0.2] \tikzstyle{every node}+=[inner sep=0pt] \draw [black] (38.8,-19.3) circle (3); \draw (38.8,-19.3) node {$q1$}; \draw [black] (24,-19.3) circle (3); \draw (24,-19.3) node {$s$}; \draw [black] (52.1,-19.3) circle (3); \draw (52.1,-19.3) node {$qf$}; \draw [black] (52.1,-19.3) circle (2.4); \draw [black] (41.8,-19.3) — (49.1,-19.3); \fill [black] (49.1,-19.3) — (48.3,-18.8) — (48.3,-19.8); \draw (45.45,-19.8) node [below] {$ϵ,z|z$}; \draw [black] (19.6,-19.3) — (21,-19.3); \fill [black] (21,-19.3) — (20.2,-18.8) — (20.2,-19.8); \draw [black] (37.477,-16.62) arc (234:-54:2.25); \draw (38.8,-12.05) node [above] {$1,0|ϵ$}; \fill [black] (40.12,-16.62) — (41,-16.27) — (40.19,-15.68); \draw [black] (21.323,-17.972) arc (271.34936:-16.65064:2.25); \draw (17.17,-13.44) node [above] {$0,z|0z$}; \fill [black] (23.43,-16.37) — (23.91,-15.56) — (22.91,-15.58); \draw [black] (24.533,-16.36) arc (197.46683:-90.53317:2.25); \draw (30.75,-13.38) node [above] {$0,0|00$}; \fill [black] (26.66,-17.93) — (27.57,-18.17) — (27.27,-17.22); \draw [black] (27,-19.3) — (35.8,-19.3); \fill [black] (35.8,-19.3) — (35,-18.8) — (35,-19.8); \draw (31.4,-19.8) node [below] {$1,0|ϵ$}; \end{tikzpicture} \end{center}\par $[\text{Eg: }|w_0|=|w_1|]$ \begin{center} \begin{tikzpicture}[scale=0.2] \tikzstyle{every node}+=[inner sep=0pt] \draw [black] (46.8,-18.8) circle (3); \draw (46.8,-18.8) node {$qf$}; \draw [black] (46.8,-18.8) circle (2.4); \draw [black] (30.8,-18.8) circle (3); \draw (30.8,-18.8) node {$s$}; \draw [black] (33.8,-18.8) — (43.8,-18.8); \fill [black] (43.8,-18.8) — (43,-18.3) — (43,-19.3); \draw (38.8,-18.3) node [above] {$ϵ,z|z$}; \draw [black] (28.691,-16.683) arc (252.63003:-35.36997:2.25); \draw (23.64,-11.71) node [above] {$0,z|0z;\text{mbox}1,z|1z$}; \fill [black] (31.2,-15.84) — (31.91,-15.22) — (30.96,-14.93); \draw [black] (30.401,-15.838) arc (215.40194:-72.59806:2.25); \draw (38.06,-11.7) node [above] {$0,0|00;\text{mbox}1,1|11$}; \fill [black] (32.91,-16.68) — (33.85,-16.63) — (33.27,-15.81); \draw [black] (32.123,-21.48) arc (54:-234:2.25); \draw (30.8,-26.05) node [below] {$0,1|ϵ;\text{mbox}1,0|ϵ$}; \fill [black] (29.48,-21.48) — (28.6,-21.83) — (29.41,-22.42); \draw [black] (26.7,-18.8) — (27.8,-18.8); \fill [black] (27.8,-18.8) — (27,-18.3) — (27,-19.3); \end{tikzpicture} \end{center}

\end{enumerate}

{[\bfseries From CFGs:]} \begin{enumerate} \item {[Ground:]} $[(s,ϵ,z):(q_{\text{loop}},zS)]$ \item {[Terminals:]} $[(q,0,0):(q,ϵ)]$ \item {[Non Terminals:]} $[(q,ϵ,A):(q,...)]$ \item {[Return:]} $[(q_{\text{loop}},ϵ,z):(qf,z)]$\par \begin{center} \begin{tikzpicture}[scale=0.2] \tikzstyle{every node}+=[inner sep=0pt] \draw [black] (38.8,-19.3) circle (3); \draw (38.8,-19.3) node {$q_{\text{loop}}$}; \draw [black] (24.3,-19.3) circle (3); \draw (24.3,-19.3) node {$s$}; \draw [black] (52.9,-19.3) circle (3); \draw (52.9,-19.3) node {$qf$}; \draw [black] (52.9,-19.3) circle (2.4); \draw [black] (24.3,-27.8) circle (3); \draw (24.3,-27.8) node {$...$}; \draw [black] (52.9,-27.8) circle (3); \draw (52.9,-27.8) node {$...$}; \draw [black] (41.8,-19.3) — (49.9,-19.3); \fill [black] (49.9,-19.3) — (49.1,-18.8) — (49.1,-19.8); \draw (45.85,-18.8) node [above] {$ϵ,z|z$}; \draw [black] (19.9,-19.3) — (21.3,-19.3); \fill [black] (21.3,-19.3) — (20.5,-18.8) — (20.5,-19.8); \draw [black] (27.3,-19.3) — (35.8,-19.3); \fill [black] (35.8,-19.3) — (35,-18.8) — (35,-19.8); \draw (31.55,-18.8) node [above] {$ϵ,z|zS$}; \draw [black] (36.21,-20.82) — (26.89,-26.28); \fill [black] (26.89,-26.28) — (27.83,-26.31) — (27.33,-25.45); \draw (34.22,-24.05) node [below] {$ϵ,S|...$}; \draw [black] (39.362,-22.231) arc (0.75792:-119.99967:8.519); \fill [black] (39.36,-22.23) — (38.87,-23.04) — (39.87,-23.02); \draw (36.4,-30.19) node [below] {$...$}; \draw [black] (37.477,-16.62) arc (234:-54:2.25); \draw (38.8,-12.05) node [above] {$0,0|ϵ$}; \fill [black] (40.12,-16.62) — (41,-16.27) — (40.19,-15.68); \draw [black] (50.644,-29.752) arc (-59.47709:-182.68916:8.307); \fill [black] (38.13,-22.21) — (37.59,-22.98) — (38.59,-23.03); \draw (40.89,-30.21) node [below] {$...$}; \draw [black] (41.37,-20.85) — (50.33,-26.25); \fill [black] (50.33,-26.25) — (49.9,-25.41) — (49.39,-26.27); \draw (43.01,-24.05) node [below] {$ϵ,A|...$}; \end{tikzpicture} \end{center} \end{enumerate} {[\bfseries Compromise:]} $[Eg:w{w}^R]$ \begin{center} \begin{tikzpicture}[scale=0.2] \tikzstyle{every node}+=[inner sep=0pt] \draw [black] (41.9,-19.3) circle (3); \draw (41.9,-19.3) node {$q1$}; \draw [black] (16.9,-19.3) circle (3); \draw (16.9,-19.3) node {$s$}; \draw [black] (57.7,-19.3) circle (3); \draw (57.7,-19.3) node {$qf$}; \draw [black] (57.7,-19.3) circle (2.4); \draw [black] (44.9,-19.3) — (54.7,-19.3); \fill [black] (54.7,-19.3) — (53.9,-18.8) — (53.9,-19.8); \draw (49.8,-18.8) node [above] {$ϵ,z|z$}; \draw [black] (12.5,-19.3) — (13.9,-19.3); \fill [black] (13.9,-19.3) — (13.1,-18.8) — (13.1,-19.8); \draw [black] (19.822,-18.622) arc (101.31043:78.68957:48.837); \fill [black] (38.98,-18.62) — (38.29,-17.97) — (38.1,-18.96); \draw (29.4,-17.17) node [above] {$ϵ,z|z$}; \draw [black] (39.697,-17.281) arc (255.23442:-32.76558:2.25); \draw (37.16,-12.46) node [above] {$0,0|ϵ$}; \fill [black] (42.16,-16.32) — (42.85,-15.68) — (41.88,-15.42); \draw [black] (18.223,-21.98) arc (54:-234:2.25); \draw (16.9,-26.55) node [below] {$0,z|0z;1,z|1z$}; \fill [black] (15.58,-21.98) — (14.7,-22.33) — (15.51,-22.92); \draw [black] (16.639,-16.323) arc (212.74091:-75.25909:2.25); \draw (25.21,-12.38) node [above] {$0,0|00;1,1|11$}; \fill [black] (19.1,-17.28) — (20.05,-17.27) — (19.51,-16.43); \draw [black] (14.722,-17.254) arc (254.51455:-33.48545:2.25); \draw (8.71,-12.33) node [above] {$0,1|01;1,0|10$}; \fill [black] (17.2,-16.33) — (17.89,-15.69) — (16.93,-15.42); \draw [black] (38.979,-19.98) arc (-78.66597:-101.33403:48.738); \fill [black] (38.98,-19.98) — (38.1,-19.65) — (38.29,-20.63); \draw (29.4,-21.43) node [below] {$ϵ,0|0$}; \draw [black] (39.502,-21.097) arc (-57.69488:-122.30512:18.902); \fill [black] (39.5,-21.1) — (38.56,-21.1) — (39.09,-21.95); \draw (29.4,-24.52) node [below] {$ϵ,1|1$}; \draw [black] (41.573,-16.33) arc (214.01689:-73.98311:2.25); \draw (46.45,-12.39) node [above] {$1,1|ϵ$}; \fill [black] (44.06,-17.23) — (45,-17.2) — (44.44,-16.37); \end{tikzpicture} \end{center} \subsection{Non CFLs} [“sufficiently long strings in a CFLs may be pumped—that is, have a middle section of the word repeated an arbitrary number of times—to produce a new word that also lies within the same language thus exists a constant $p$ such that any word $w$ in $L$ with length at least $p$ can be split into five substrings, $w=uvxyz$ where the middle strings $v$ and $y$ must not be empty, such that the words constructed by repeating $v$ and $y$ zero or more times are still in $L$, moreover, guarantees that the length of $uxy$ will be at most $p$, imposing a limit on the ways in which $w$ may be split”] $[Ex:0^n{1}^n{2}^n,\to 0^p{1}^p{2}^p:|uvx|\le p\to v=0^x]$ \chapter{Computability Theory} \section{Turing Machine} {\bfseries [Informal:]}\par[maneuvers the symbols on a strip of infinite tape]\par [{\bfseries Formal:}]\par [a TM is a septuple $(K,\Sigma ,\Gamma ,\delta ,s,b,H)$ where] \begin{enumerate} \item {[$K$ is a finite set of states]} \item {[$\Sigma$ is an input alphabet]} \item {[$\Gamma$ is a tape alphabet, optionally $\Delta \in \Gamma$]} \item {[$b\in \{\#\}\subset \Gamma$} is the empty tape symbol] \item {[$s\in K$ is the initial state]} \item {[$H\in \{y,n\}\subset K$ is the set of halting states]} \item {[$\delta$ is the transition function, $(K-H)\times \Gamma \to K\times (\Gamma \cup \{L,R\})$]} \end{enumerate} [a string in $w\in {\Sigma }^{\ast }$ is said to be accepted if and only if such that $(s,\Delta \underline{\#}w{\#}^{\ast }){⊢}_M^{\ast }(y,\underline{xxx})$ where]\par [${⊢}_M^{\ast }$ is reflexive, transitive closure of the one move binary relation ${⊢}_M:K\times {\underline{\Gamma }}^{+}\to K\times {\underline{\Gamma }}^{+}$, meanwhile]\par [counters are rejections or loops] $[f_{\text{halt}}(w)=[\text{final tape}]]$ \subsection{Construction Of TM} [automataic notation] \begin{enumerate} \item {[Eg: $0^n{1}^n{2}^n,n\ge 0$]} \begin{center} \begin{tikzpicture}[scale=0.2] \tikzstyle{every node}+=[inner sep=0pt] \draw [black] (12.3,-20.2) circle (3); \draw (12.3,-20.2) node {$s$}; \draw [black] (25.5,-20.2) circle (3); \draw (25.5,-20.2) node {$q0$}; \draw [black] (41.4,-20.2) circle (3); \draw (41.4,-20.2) node {$q1$}; \draw [black] (56.1,-20.2) circle (3); \draw (56.1,-20.2) node {$q2$}; \draw [black] (70.4,-20.2) circle (3); \draw (70.4,-20.2) node {$q3$}; \draw [black] (25.5,-34.6) circle (3); \draw (25.5,-34.6) node {$Y$}; \draw [black] (25.5,-34.6) circle (2.4); \draw [black] (8,-20.2) — (9.3,-20.2); \fill [black] (9.3,-20.2) — (8.5,-19.7) — (8.5,-20.7); \draw [black] (15.3,-20.2) — (22.5,-20.2); \fill [black] (22.5,-20.2) — (21.7,-19.7) — (21.7,-20.7); \draw (18.9,-20.7) node [below] {$\#|\#,R$}; \draw [black] (39.601,-17.814) arc (244.75575:-43.24425:2.25); \draw (38.77,-12.83) node [above] {$0|0,R$}; \fill [black] (42.2,-17.32) — (42.99,-16.81) — (42.09,-16.38); \draw [black] (40.751,-17.283) arc (220.27712:-67.72288:2.25); \draw (45.16,-12.92) node [above] {$X|X,R$}; \fill [black] (43.32,-17.91) — (44.25,-17.77) — (43.61,-17.01); \draw [black] (28.5,-20.2) — (38.4,-20.2); \fill [black] (38.4,-20.2) — (37.6,-19.7) — (37.6,-20.7); \draw (33.45,-20.7) node [below] {$0|X,R$}; \draw [black] (24.177,-17.52) arc (234:-54:2.25); \draw (25.5,-12.95) node [above] {$X|X,R$}; \fill [black] (26.82,-17.52) — (27.7,-17.17) — (26.89,-16.58); \draw [black] (44.4,-20.2) — (53.1,-20.2); \fill [black] (53.1,-20.2) — (52.3,-19.7) — (52.3,-20.7); \draw (48.75,-20.7) node [below] {$1|X,R$}; \draw [black] (55.447,-17.284) arc (220.36135:-67.63865:2.25); \draw (59.83,-12.92) node [above] {$X|X,R$}; \fill [black] (58.02,-17.91) — (58.95,-17.77) — (58.3,-17.01); \draw [black] (54.251,-17.852) arc (245.95234:-42.04766:2.25); \draw (53.13,-12.88) node [above] {$1|1,R$}; \fill [black] (56.84,-17.3) — (57.62,-16.78) — (56.71,-16.37); \draw [black] (59.1,-20.2) — (67.4,-20.2); \fill [black] (67.4,-20.2) — (66.6,-19.7) — (66.6,-20.7); \draw (63.25,-20.7) node [below] {$2|X,L$}; \draw [black] (69.077,-17.52) arc (234:-54:2.25); \draw (70.4,-12.95) node [above] {${\#}^{\prime }|{\#}^{\prime },L$}; \fill [black] (71.72,-17.52) — (72.6,-17.17) — (71.79,-16.58); \draw [black] (67.833,-21.752) arc (-60.94297:-119.05703:40.939); \fill [black] (28.07,-21.75) — (28.52,-22.58) — (29.01,-21.7); \draw (47.95,-27.4) node [below] {$\#|\#,R$}; \draw [black] (25.5,-23.2) — (25.5,-31.6); \fill [black] (25.5,-31.6) — (26,-30.8) — (25,-30.8); \draw (25,-27.4) node [left] {$\#,\#,R$}; \end{tikzpicture} \end{center} \item {[Eg: $\#w{\underline{\#}}^{\ast }\to \underline{\#}w\#w^R{\#}^{\ast }$]} \begin{center} \begin{tikzpicture}[scale=0.2] \tikzstyle{every node}+=[inner sep=0pt] \draw [black] (7.9,-25.6) circle (3); \draw (7.9,-25.6) node {$s$}; \draw [black] (20.9,-25.6) circle (3); \draw (20.9,-25.6) node {$q0$}; \draw [black] (28.4,-15.4) circle (3); \draw (28.4,-15.4) node {$q1$}; \draw [black] (28.4,-35.8) circle (3); \draw (28.4,-35.8) node {$q2$}; \draw [black] (42.2,-15.4) circle (3); \draw (42.2,-15.4) node {$q3$}; \draw [black] (42.2,-35.8) circle (3); \draw (42.2,-35.8) node {$q4$}; \draw [black] (54.9,-15.4) circle (3); \draw (54.9,-15.4) node {$q5$}; \draw [black] (54.9,-35.8) circle (3); \draw (54.9,-35.8) node {$q6$}; \draw [black] (7.9,-35.8) circle (3); \draw (7.9,-35.8) node {$qf$}; \draw [black] (7.9,-35.8) circle (2.4); \draw [black] (3.6,-25.6) — (4.9,-25.6); \fill [black] (4.9,-25.6) — (4.1,-25.1) — (4.1,-26.1); \draw [black] (10.9,-25.6) — (17.9,-25.6); \fill [black] (17.9,-25.6) — (17.1,-25.1) — (17.1,-26.1); \draw (14.4,-25.1) node [above] {$\#|\#,L$}; \draw [black] (22.68,-23.18) — (26.62,-17.82); \fill [black] (26.62,-17.82) — (25.75,-18.17) — (26.55,-18.76); \draw (25.23,-21.89) node [right] {$0|x,R$}; \draw [black] (22.68,-28.02) — (26.62,-33.38); \fill [black] (26.62,-33.38) — (26.55,-32.44) — (25.75,-33.03); \draw (25.23,-29.31) node [right] {$1|x,R$}; \draw [black] (27.077,-12.72) arc (234:-54:2.25); \draw (28.4,-8.15) node [above] {${\#}^{\prime }|{\#}^{\prime },R$}; \fill [black] (29.72,-12.72) — (30.6,-12.37) — (29.79,-11.78); \draw [black] (29.723,-38.48) arc (54:-234:2.25); \draw (28.4,-43.05) node [below] {${\#}^{\prime }|{\#}^{\prime },R$}; \fill [black] (27.08,-38.48) — (26.2,-38.83) — (27.01,-39.42); \draw [black] (31.4,-35.8) — (39.2,-35.8); \fill [black] (39.2,-35.8) — (38.4,-35.3) — (38.4,-36.3); \draw (35.3,-35.3) node [above] {$\#|\#,R$}; \draw [black] (31.4,-15.4) — (39.2,-15.4); \fill [black] (39.2,-15.4) — (38.4,-14.9) — (38.4,-15.9); \draw (35.3,-15.9) node [below] {$\#|\#,R$}; \draw [black] (45.2,-15.4) — (51.9,-15.4); \fill [black] (51.9,-15.4) — (51.1,-14.9) — (51.1,-15.9); \draw (48.55,-15.9) node [below] {$\#|0,L$}; \draw [black] (45.2,-35.8) — (51.9,-35.8); \fill [black] (51.9,-35.8) — (51.1,-35.3) — (51.1,-36.3); \draw (48.55,-35.3) node [above] {$\#|1,L$}; \draw [black] (52.367,-17.007) arc (-59.03533:-87.56618:60.307); \fill [black] (23.9,-25.55) — (24.72,-26.01) — (24.68,-25.01); \draw (40.81,-23.68) node [below] {$x|0,L$}; \draw [black] (23.896,-25.754) arc (85.79733:60.80418:68.558); \fill [black] (23.9,-25.75) — (24.66,-26.31) — (24.73,-25.31); \draw (40.71,-27.84) node [above] {$x|1,L$}; \draw [black] (53.577,-12.72) arc (234:-54:2.25); \draw (54.9,-8.15) node [above] {$0|0,L;\text{mbox}1|1,L;\text{mbox}\#|\#,L$}; \fill [black] (56.22,-12.72) — (57.1,-12.37) — (56.29,-11.78); \draw [black] (56.223,-38.48) arc (54:-234:2.25); \draw (54.9,-43.05) node [below] {$0|0,L;\text{mbox}1|1,L;\text{mbox}\#|\#,L$}; \fill [black] (53.58,-38.48) — (52.7,-38.83) — (53.51,-39.42); \draw [black] (18.54,-27.45) — (10.26,-33.95); \fill [black] (10.26,-33.95) — (11.2,-33.85) — (10.58,-33.06); \draw (17.63,-31.2) node [below] {$\#|\#,N$}; \end{tikzpicture} \end{center} \item {[Eg: $\#\#w{\underline{\#}}^{\ast }\to \underline{\#}w+1{\#}^{\ast }$]} \begin{center} \begin{tikzpicture}[scale=0.2] \tikzstyle{every node}+=[inner sep=0pt] \draw [black] (15.2,-20.2) circle (3); \draw (15.2,-20.2) node {$q0$}; \draw [black] (28.5,-20.2) circle (3); \draw (28.5,-20.2) node {$q1$}; \draw [black] (41.8,-20.2) circle (3); \draw (41.8,-20.2) node {$q2$}; \draw [black] (55.1,-20.2) circle (3); \draw (55.1,-20.2) node {$qf1$}; \draw [black] (55.1,-20.2) circle (2.4); \draw [black] (28.5,-29.9) circle (3); \draw (28.5,-29.9) node {$qf2$}; \draw [black] (28.5,-29.9) circle (2.4); \draw [black] (10.9,-20.2) — (12.2,-20.2); \fill [black] (12.2,-20.2) — (11.4,-19.7) — (11.4,-20.7); \draw [black] (18.2,-20.2) — (25.5,-20.2); \fill [black] (25.5,-20.2) — (24.7,-19.7) — (24.7,-20.7); \draw (21.85,-19.7) node [above] {$\#|\#,L$}; \draw [black] (27.177,-17.52) arc (234:-54:2.25); \draw (28.5,-12.95) node [above] {$1|0,L$}; \fill [black] (29.82,-17.52) — (30.7,-17.17) — (29.89,-16.58); \draw [black] (31.5,-20.2) — (38.8,-20.2); \fill [black] (38.8,-20.2) — (38,-19.7) — (38,-20.7); \draw (35.15,-19.7) node [above] {$0|1,L$}; \draw [black] (44.8,-20.2) — (52.1,-20.2); \fill [black] (52.1,-20.2) — (51.3,-19.7) — (51.3,-20.7); \draw (48.45,-19.7) node [above] {$\#|\#,L$}; \draw [black] (28.5,-23.2) — (28.5,-26.9); \fill [black] (28.5,-26.9) — (29,-26.1) — (28,-26.1); \draw (28,-25.05) node [left] {$\#|1,L$}; \draw [black] (40.477,-17.52) arc (234:-54:2.25); \draw (41.8,-12.95) node [above] {${\#}^{\prime }|{\#}^{\prime },L$}; \fill [black] (43.12,-17.52) — (44,-17.17) — (43.19,-16.58); \end{tikzpicture} \end{center} \item {[Eg: $w{w}^R\cup wx{w}^R$]} \begin{center} \begin{tikzpicture}[scale=0.2] \tikzstyle{every node}+=[inner sep=0pt] \draw [black] (10.6,-21.7) circle (3); \draw (10.6,-21.7) node {$s$}; \draw [black] (24.5,-21.7) circle (3); \draw (24.5,-21.7) node {$q0$}; \draw [black] (37.2,-10.6) circle (3); \draw (37.2,-10.6) node {$q1$}; \draw [black] (37.2,-32.9) circle (3); \draw (37.2,-32.9) node {$q2$}; \draw [black] (51.2,-32.9) circle (3); \draw (51.2,-32.9) node {$q4$}; \draw [black] (51.2,-10.6) circle (3); \draw (51.2,-10.6) node {$q3$}; \draw [black] (64.1,-21.7) circle (3); \draw (64.1,-21.7) node {$q5$}; \draw [black] (42.7,-21.7) circle (3); \draw (42.7,-21.7) node {$Y$}; \draw [black] (42.7,-21.7) circle (2.4); \draw [black] (6.2,-21.7) — (7.6,-21.7); \fill [black] (7.6,-21.7) — (6.8,-21.2) — (6.8,-22.2); \draw [black] (13.6,-21.7) — (21.5,-21.7); \fill [black] (21.5,-21.7) — (20.7,-21.2) — (20.7,-22.2); \draw (17.55,-22.2) node [below] {$\#|\#,R$}; \draw [black] (26.76,-19.73) — (34.94,-12.57); \fill [black] (34.94,-12.57) — (34.01,-12.72) — (34.67,-13.48); \draw (27.89,-15.66) node [above] {$0|\#,R$}; \draw [black] (26.75,-23.68) — (34.95,-30.92); \fill [black] (34.95,-30.92) — (34.68,-30.01) — (34.02,-30.76); \draw (28.17,-27.79) node [below] {$1|\#,R$}; \draw [black] (40.2,-10.6) — (48.2,-10.6); \fill [black] (48.2,-10.6) — (47.4,-10.1) — (47.4,-11.1); \draw (44.2,-11.1) node [below] {$\#|\#,L$}; \draw [black] (40.2,-32.9) — (48.2,-32.9); \fill [black] (48.2,-32.9) — (47.4,-32.4) — (47.4,-33.4); \draw (44.2,-32.4) node [above] {$\#|\#,L$}; \draw [black] (53.47,-30.93) — (61.83,-23.67); \fill [black] (61.83,-23.67) — (60.9,-23.81) — (61.56,-24.57); \draw (60.61,-27.79) node [below] {$1|\#,L$}; \draw [black] (53.47,-12.56) — (61.83,-19.74); \fill [black] (61.83,-19.74) — (61.55,-18.84) — (60.89,-19.6); \draw (60.61,-15.66) node [above] {$0|\#,L$}; \draw [black] (64.508,-24.669) arc (3.57753:-183.57753:20.247); \fill [black] (24.09,-24.67) — (23.54,-25.44) — (24.54,-25.5); \draw (44.3,-46.68) node [below] {$\#|\#,R$}; \draw [black] (66.78,-20.377) arc (144:-144:2.25); \draw (71.35,-21.7) node [right] {${\#}^{\prime }|{\#}^{\prime },L$}; \fill [black] (66.78,-23.02) — (67.13,-23.9) — (67.72,-23.09); \draw [black] (27.5,-21.7) — (39.7,-21.7); \fill [black] (39.7,-21.7) — (38.9,-21.2) — (38.9,-22.2); \draw (33.6,-21.2) node [above] {$\#|\#,N$}; \draw [black] (49.38,-12.98) — (44.52,-19.32); \fill [black] (44.52,-19.32) — (45.41,-18.99) — (44.61,-18.38); \draw (47.52,-17.56) node [right] {$\#|\#,N$}; \draw [black] (49.39,-30.51) — (44.51,-24.09); \fill [black] (44.51,-24.09) — (44.6,-25.03) — (45.4,-24.42); \draw (47.52,-25.9) node [right] {$\#|\#,N$}; \draw [black] (38.523,-35.58) arc (54:-234:2.25); \draw (37.2,-40.15) node [below] {${\#}^{\prime }|{\#}^{\prime },R$}; \fill [black] (35.88,-35.58) — (35,-35.93) — (35.81,-36.52); \draw [black] (35.877,-7.92) arc (234:-54:2.25); \draw (37.2,-3.35) node [above] {${\#}^{\prime }|{\#}^{\prime },R$}; \fill [black] (38.52,-7.92) — (39.4,-7.57) — (38.59,-6.98); \end{tikzpicture} \end{center} \end{enumerate} [algorithmic notation] \begin{enumerate} \item {[Head Moving [$L,R$]]} $[\delta (s,\Gamma )=(H,L\text{ or }R);L_x,R_x]$ \item {[Symbol Writing [$0\in \Sigma$]]} $[\delta (s,\Gamma )=(H,\Gamma )]$ \item {[Accepting and Rejecting: [$y,n$]]} $[\delta (s,\Gamma )=(Y|N,\Gamma )]$ \item {[Combining Rules:]} $[[M_1][\to (0)M_2][\to (1)M_3]\dots ]$ [“start in initial state of $M_1$, operate as $M_1$ would operate until $M_1$ would halt, then if the scanned symbol is an $0$, imitate $M_2$, otherwise if the scanned symbol is a $1$ initiate $M_3$ so on”] \item {[Eg: $0^n{1}^n{2}^n,n\ge 0]$} \begin{center} \begin{tikzpicture}[scale=0.2] \tikzstyle{every node}+=[inner sep=0pt] \draw (5.2,-20.2) node {$R$}; \draw (15.1,-20.2) node {$X$}; \draw (22.4,-20.2) node {$R$}; \draw (31.7,-20.2) node {$X$}; \draw (38.9,-20.2) node {$R$}; \draw (48.2,-20.2) node {$X{L}_{\#}$}; \draw (5.2,-30.7) node {$Y$}; \draw (22.4,-30.7) node {$N$}; \draw [black] (0.9,-20.2) — (2.2,-20.2); \fill [black] (2.2,-20.2) — (1.4,-19.7) — (1.4,-20.7); \draw [black] (37.577,-17.52) arc (234:-54:2.25); \draw (38.9,-12.95) node [above] {$1,X$}; \fill [black] (40.22,-17.52) — (41.1,-17.17) — (40.29,-16.58); \draw [black] (21.077,-17.52) arc (234:-54:2.25); \draw (22.4,-12.95) node [above] {$0,X$}; \fill [black] (23.72,-17.52) — (24.6,-17.17) — (23.79,-16.58); \draw [black] (3.877,-17.52) arc (234:-54:2.25); \draw (5.2,-12.95) node [above] {$X$}; \fill [black] (6.52,-17.52) — (7.4,-17.17) — (6.59,-16.58); \draw [black] (8.2,-20.2) — (12.1,-20.2); \fill [black] (12.1,-20.2) — (11.3,-19.7) — (11.3,-20.7); \draw (10.15,-19.7) node [above] {$0$}; \draw [black] (18.1,-20.2) — (19.4,-20.2); \fill [black] (19.4,-20.2) — (18.6,-19.7) — (18.6,-20.7); \draw [black] (25.4,-20.2) — (28.7,-20.2); \fill [black] (28.7,-20.2) — (27.9,-19.7) — (27.9,-20.7); \draw (27.05,-19.7) node [above] {$1$}; \draw [black] (34.7,-20.2) — (35.9,-20.2); \fill [black] (35.9,-20.2) — (35.1,-19.7) — (35.1,-20.7); \draw [black] (41.9,-20.2) — (45.2,-20.2); \fill [black] (45.2,-20.2) — (44.4,-19.7) — (44.4,-20.7); \draw (43.55,-19.7) node [above] {$2$}; \draw [black] (5.2,-23.2) — (5.2,-27.7); \fill [black] (5.2,-27.7) — (5.7,-26.9) — (4.7,-26.9); \draw (4.7,-25.45) node [left] {$\#$}; \draw [black] (22.4,-23.2) — (22.4,-27.7); \fill [black] (22.4,-27.7) — (22.9,-26.9) — (21.9,-26.9); \draw (21.9,-25.45) node [left] {$\#,2$}; \draw [black] (36.37,-21.81) — (24.93,-29.09); \fill [black] (24.93,-29.09) — (25.87,-29.08) — (25.34,-28.24); \draw (32.68,-25.95) node [below] {$\#,0$}; \draw [black] (47.051,-22.969) arc (-26.31628:-153.68372:22.704); \fill [black] (6.35,-22.97) — (6.26,-23.91) — (7.15,-23.46); \draw [black] (7.76,-21.76) — (19.84,-29.14); \fill [black] (19.84,-29.14) — (19.42,-28.29) — (18.9,-29.15); \draw (12.05,-25.95) node [below] {$1,2$}; \end{tikzpicture} \end{center} \item {[Eg:$w{w}^R\cup wx{w}^R$]} \begin{center} \begin{tikzpicture}[scale=0.2] \tikzstyle{every node}+=[inner sep=0pt] \draw (22.9,-21.7) node {$R$}; \draw (36.5,-21.7) node {$R_{\#}L$}; \draw (51.7,-21.7) node {$\#L_{\#}$}; \draw (22.9,-32.9) node {$Y$}; \draw (36.5,-32.9) node {$N$}; \draw [black] (18.4,-21.7) — (19.9,-21.7); \fill [black] (19.9,-21.7) — (19.1,-21.2) — (19.1,-22.2); \draw [black] (25.9,-21.7) — (33.5,-21.7); \fill [black] (33.5,-21.7) — (32.7,-21.2) — (32.7,-22.2); \draw (29.7,-21.2) node [above] {$\{0,1\}$}; \draw [black] (39.5,-21.7) — (48.7,-21.7); \fill [black] (48.7,-21.7) — (47.9,-21.2) — (47.9,-22.2); \draw (44.1,-21.2) node [above] {$\{0,1\}$}; \draw [black] (22.9,-24.7) — (22.9,-29.9); \fill [black] (22.9,-29.9) — (23.4,-29.1) — (22.4,-29.1); \draw (22.4,-27.3) node [left] {$\#$}; \draw [black] (34.18,-23.61) — (25.22,-30.99); \fill [black] (25.22,-30.99) — (26.15,-30.87) — (25.52,-30.1); \draw (30.99,-27.79) node [below] {$\#$}; \draw [black] (36.5,-24.7) — (36.5,-29.9); \fill [black] (36.5,-29.9) — (37,-29.1) — (36,-29.1); \draw (37,-27.3) node [right] {$\{1,0\}$}; \draw [black] (25.061,-19.624) arc (129.39709:50.60291:19.283); \fill [black] (25.06,-19.62) — (26,-19.5) — (25.36,-18.73); \end{tikzpicture} \end{center} \item {[$\#w\underline{\#}\to \#w\#w\underline{\#}$]} \begin{center} \begin{tikzpicture}[scale=0.2] \tikzstyle{every node}+=[inner sep=0pt] \draw (19.8,-20.1) node {$L_{\#}$}; \draw (27.6,-20.1) node {$R$}; \draw (42.2,-20.1) node {$\#R_{\#}^2\{a,b\}{L}_{\#}^2\{a,b\}$}; \draw (27.6,-28.7) node {$R_{\#}$}; \draw [black] (22.8,-20.1) — (24.6,-20.1); \fill [black] (24.6,-20.1) — (23.8,-19.6) — (23.8,-20.6); \draw [black] (30.6,-20.1) — (39.2,-20.1); \fill [black] (39.2,-20.1) — (38.4,-19.6) — (38.4,-20.6); \draw (34.9,-19.6) node [above] {$\{0,1\}$}; \draw [black] (27.6,-23.1) — (27.6,-25.7); \fill [black] (27.6,-25.7) — (28.1,-24.9) — (27.1,-24.9); \draw (28.1,-24.4) node [right] {$\#$}; \draw [black] (29.344,-17.68) arc (133.5691:46.4309:8.062); \fill [black] (29.34,-17.68) — (30.27,-17.49) — (29.58,-16.77); \draw [black] (15.6,-20.1) — (16.8,-20.1); \fill [black] (16.8,-20.1) — (16,-19.6) — (16,-20.6); \end{tikzpicture} \end{center} \end{enumerate} \subsection{Variants Of TM} \begin{enumerate} \item {[Multitape TM]} $[\delta :(K-H)\times {\Gamma }^k\to K\times {\Gamma }^k\times \{L,R{\}}^k]$ \begin{enumerate} \item {[Copying]} $[(\underline{\#}w{\#}^{\ast },{\underline{\#}}^{\ast }):(\#w{\underline{\#}}^{\ast },\#w{\underline{\#}}^{\ast }):(\#w{\underline{\#}}^{\ast },\underline{\#}w{\#}^{\ast }):(\#w\#w{\underline{\#}}^{\ast },\#w{\underline{\#}}^{\ast })]$ \begin{center} \begin{tikzpicture}[scale=0.2] \tikzstyle{every node}+=[inner sep=0pt] \draw (24.6,-19.6) node {$\{0,1{\}}^2$}; \draw (8,-19.6) node {$R^{1,2}$}; \draw (36.3,-19.6) node {$L_{\#}^2\to R^{1,2}$}; \draw (52.2,-19.6) node {$\{0,1{\}}^1$}; \draw [black] (11,-19.6) — (21.6,-19.6); \fill [black] (21.6,-19.6) — (20.8,-19.1) — (20.8,-20.1); \draw (16.3,-19.1) node [above] {$\{0,1{\}}^1$}; \draw [black] (9.802,-17.218) arc (133.74578:46.25422:9.397); \fill [black] (9.8,-17.22) — (10.73,-17.03) — (10.03,-16.3); \draw [black] (33.985,-21.504) arc (-54.74715:-125.25285:20.505); \fill [black] (33.99,-21.5) — (33.04,-21.56) — (33.62,-22.37); \draw (22.15,-25.76) node [below] {${\#}^1$}; \draw [black] (39.3,-19.6) — (49.2,-19.6); \fill [black] (49.2,-19.6) — (48.4,-19.1) — (48.4,-20.1); \draw (44.25,-19.1) node [above] {$\{a,b{\}}^2$}; \draw [black] (37.989,-17.139) arc (135.70981:44.29019:8.746); \fill [black] (37.99,-17.14) — (38.91,-16.92) — (38.19,-16.22); \end{tikzpicture} \end{center} \item {[Binary Addition]} $[(\#w_1;w_2{\underline{\#}}^{\ast },{\underline{\#}}^{\ast })\to (\#{\underline{0}}^{\ast }{w}_1+w_2{\underline{\#}}^{\ast },\underline{\#}{w}_1{\#}^{\ast })]$ \begin{center} \begin{tikzpicture}[scale=0.2] \tikzstyle{every node}+=[inner sep=0pt] \draw (29.4,-19.6) node {$0^1\{0,1{\}}^2$}; \draw (12.4,-19.6) node {$R^{1,2}$}; \draw (46.4,-19.6) node {$0^1{R}_{\#}^1{L}^{1,2}$}; \draw (46.4,-8.1) node {$0^1$}; \draw (61.7,-19.6) node {$1^1$}; \draw (46.4,-37.8) node {$L^{1,2}$}; \draw (61.7,-37.8) node {$0^1$}; \draw (46.4,-49.3) node {$1^1$}; \draw (39.1,-29.2) node {$0^1$}; \draw (54.8,-29.2) node {$1^1$}; \draw [black] (15.4,-19.6) — (26.4,-19.6); \fill [black] (26.4,-19.6) — (25.6,-19.1) — (25.6,-20.1); \draw (20.9,-19.1) node [above] {$\{0,1{\}}^1$}; \draw [black] (14.235,-17.241) arc (133.28317:46.71683:9.722); \fill [black] (14.23,-17.24) — (15.16,-17.06) — (14.47,-16.33); \draw [black] (43.912,-21.273) arc (-59.1227:-120.8773:28.277); \fill [black] (43.91,-21.27) — (42.97,-21.25) — (43.48,-22.11); \draw (29.4,-25.78) node [below] {${;}^1$}; \draw [black] (48.103,-10.549) arc (24.15268:-24.15268:8.067); \fill [black] (48.1,-17.15) — (48.89,-16.63) — (47.97,-16.22); \draw [black] (44.761,-17.107) arc (-156.99668:-203.00332:8.333); \fill [black] (44.76,-10.59) — (43.99,-11.13) — (44.91,-11.53); \draw (43.6,-13.85) node [left] {$00$}; \draw [black] (49.083,-18.27) arc (110.35514:69.64486:14.28); \fill [black] (59.02,-18.27) — (58.44,-17.52) — (58.09,-18.46); \draw (54.05,-16.88) node [above] {$01,10$}; \draw [black] (59.031,-20.956) arc (-69.19376:-110.80624:14.021); \fill [black] (49.07,-20.96) — (49.64,-21.71) — (49.99,-20.77); \draw [black] (58.927,-38.935) arc (-72.91938:-107.08062:16.605); \fill [black] (58.93,-38.93) — (58.02,-38.69) — (58.31,-39.65); \draw (54.05,-40.17) node [below] {$01,10$}; \draw [black] (48.986,-36.293) arc (113.46519:66.53481:12.717); \fill [black] (48.99,-36.29) — (49.92,-36.43) — (49.52,-35.52); \draw [black] (44.643,-46.891) arc (-154.83843:-205.16157:7.857); \fill [black] (44.64,-46.89) — (44.76,-45.95) — (43.85,-46.38); \draw (43.4,-43.55) node [left] {$11$}; \draw [black] (47.98,-40.332) arc (21.97349:-21.97349:8.6); \fill [black] (47.98,-40.33) — (47.82,-41.26) — (48.74,-40.89); \draw [black] (44.58,-21.99) — (40.92,-26.81); \fill [black] (40.92,-26.81) — (41.8,-26.48) — (41,-25.87); \draw (43.32,-25.8) node [right] {$11$}; \draw [black] (41.04,-31.49) — (44.46,-35.51); \fill [black] (44.46,-35.51) — (44.32,-34.58) — (43.56,-35.23); \draw [black] (48.5,-35.65) — (52.7,-31.35); \fill [black] (52.7,-31.35) — (51.79,-31.57) — (52.5,-32.27); \draw (50.07,-32.03) node [left] {$00$}; \draw [black] (52.82,-26.94) — (48.38,-21.86); \fill [black] (48.38,-21.86) — (48.53,-22.79) — (49.28,-22.13); \end{tikzpicture} \end{center} \end{enumerate} {[Simulation:]} $[{\Gamma }^{\prime }=\Gamma \cup (\Sigma \times \{0,1\}{)}^k]$ \begin{table}[H] \centering \begin{tabular}{|c|c|c|c|c|c|c|c|} \hline $\Delta$ & $\underline{\#}$ & $x_1$ & $x_2$ & $...$ & $\#$ & $...$\ \hline $\Delta$ & $\underline{\#}$ & $y_1$ & $y_2$ & $...$ & $\#$ & $...$\ \hline \end{tabular} \begin{tabular}{|l|l|l|l|l|l|l|l|l|} \hline \multirow{4}{}{$\Delta$} & $\Delta$ & $\#$ & $x_1$ & $x_2$ & … & $\#$ & \multirow{4}{}{$\underline{\#}$} & \multirow{4}{}{…} \ \cline{2-7} & $0$ & $1$ & $0$ & $0$ & … & $0$ &&\ \cline{2-7} & $\Delta$ & $\#$ & $y_1$ & $y_2$ & … & $\#$& &\ \cline{2-7} & $0$ & $1$ & $0$ & $0$ & … & $0$ & &\ \hline \end{tabular} \end{table} \item {[Two Way TM]}$[\text{2kTM: ... ...}]$ \item {[Multiple Heads]}$[\text{2kTM: ... ..1s..}]$ \item {[Two Dimensional]}$[\dots ,\dots ,\dots ]$ \item {[Non Determinism]} \end{enumerate} \subsection{Grammars} {\bfseries[Informal]} $[\text{strings ∪ variables}]:[\text{strings ∪ variables}]$ [{\bfseries Formal:}]\par [$R$, the set of rules is a finite subset of $V^{\ast }(V-\Sigma )V^{\ast }\times V^{\ast }$] $[\text{Eg: }{a}^n{b}^n{c}^n,n>0]$ $[S\to ABCS|T_c:(ABC{)}^n{T}_c]$ $[CA\to AC,BA\to AB,CB\to BC:A^n{B}^n{C}^n{T}_c]$ $[C{T}_c=T_{c}c,C{T}_c=T_{b}c,B{T}_b=T_{b}b,B{T}_b=T_{a}b,A{T}_a=T_{a}a,T_a=e:a^n{b}^n{c}^n]$ \subsection{Recursive Function Theory} [computability of TMs in $N^k:N$] \par \begin{enumerate} \item {[Zero]}$[{\text{zero}}_k(n_1,\dots ,n_k)=0]$ \item {[Identity]} $[{\text{id}}_{k,j}(n_1,\dots ,n_j,\dots ,n_k)=n_j]$ \item {[Successor]}$[\text{succ}(n)=n+1]$\par {[Primitive Operators:]} \item {[Composition]} $[f_k(n_1,ldots,n_k)=g_l(h_1(n_1,ldots,n_k),\dots ,h_l(n_1,ldots,n_k)))]$ \item {[Recursiveness]} $[f_{k+1}(n_1,\dots ,n_k,0)=g_k(n_1,\dots ,n_k)]$ $[f_{k+1}(n_1,\dots ,n_k,m+1)=h_{k+2}(n_1,\dots ,n_k,m,f_{k+1}(n_1,\dots ,n_k,m))]$ [Minimizable:] \item {[Mu:]} $[f_k(n_1,\dots ,n_k)=\text{min}(m:g(n_1,\dots ,n_k,m)=1)|0]$ \end{enumerate} \section{Undecidibility} [excursion to upper limit of computation as TM that halts on each inputs as the precise mathematical notion of an algorithm, on principle of Church-Turing thesis, further opening up the intriguing possibly of formally proving uncomputability] \subsection{Universal Turing Machine} [one TM to rule them all] $[U("M""w")="M(w)"]$ {[Encoding:]} $["{\delta }^{\prime }s:(K-H)\times \Gamma \to K\times (\Gamma \cup \{L,R\})""w:{\Gamma }^{+}"]$ $["(q\{0,1{\}}^{\ast },a\{0,1{\}}^{\ast },q\{0,1{\}}^{\ast },a\{0,1{\}}^{\ast })""a\{0,1{\}}^{\ast }"]$ [Symbols:] $[\Delta =a\mathrm{0...0},\#=a\mathrm{0...1},L=a\mathrm{0...10},R=a\mathrm{0...11},\dots ]$ [States:] $[s=q\mathrm{0...0},y=q\mathrm{0...1},n=q\mathrm{0..10},\dots ]$ {[Simulation by 3kTM:]} $[("M","w",q_{\text{current}}\{0,1{\}}^{\ast })\to \text{[w]}\text{[q]}\to \text{[M]}\to \text{[w]}\text{[q]}\to ("M","w",q_{\text{current}}\{0,1{\}}^{\ast })]$ \subsection{The Halting Problem} \begin{enumerate} \item {[a pilot TM]} $[\text{isComputableHalts}("M""w")=[M("w")?]]$ \item {[a contrary TM]} $[\text{Dia}("M")=[\text{isHalts}("M""M"){]}^{\prime }]$ \item {[contradictions]} $[\text{Dia(Dia)}?:\text{isComputableHalts}!!!?]$ \item {[conclusions]} $[\text{ReEL}:H=\{"M""w":M\times w\}]$ \item {[recursiveness]} $\text{["L:ReL↔ L:ReEL, L’:ReEL"]}$ \text{["L:ReEL$\leftrightarroww: (s,\Delta\underline{#})\vdash_M^(q,\Delta\underline{#}w)"]}$$ $$\text{["L:ReL\leftrightarroww: (s,\Delta\underline{\#}w)\vdash_M^+(q,\Delta\underline{\#}w'$)]} \item {[monstersity]} $[\text{RuEL}:H=\{"M""w":M\underline{\times }w\}]$ \item {[followups]} \begin{enumerate} \item [Mhw?] [Mhew?] [M$=$D?] [M${}_1$M${}_2$hw?] $[\text{HALTBLANK}("M_{\text{write}}")=\text{HALT}("M""w")]$ $[\text{HALTANY}("M_{\text{erase}}")=\text{HALTBLANK}("M")]$ \item [w $\in$ L(G)?] [e $\in$ L(G)?] [L(G${}_1$)$=$L(G${}_2$)?][L(G)=$\varnothing$?] \item ~[L(TM) $=$ RL?, CFL? ReL?] \item ~[L(TM)$\in$ C $\subset$ ReELs?] \end{enumerate} \end{enumerate} \section{Languages Hierarchy} \begin{center} REL[TM, UG]$\subset$ CSL[LBA, CSG]$\subset$ CFL[PDA, CFG]$\subset$ RL[FA, RG] \end{center} \begin{table}[H] \def\arraystretch{1.3} \centering ~~~~~~~~~~\begin{tabular}{|p{3.2cm}|p{1.5cm}|p{1.5cm}|p{1.5cm}|p{1.5cm}|p{1.5cm}|p{1.5cm}|} \hline Ops & RLs & DCFLs & CFLs & CSLs & Re & RE\\hline Concat, Un, Kln& yes & \text{no}&\text{yes}&\text{yes}&\text{yes}&\text{yes}\\hline Intersection& yes & \text{no}&\text{no}&\text{yes}&\text{yes}&\text{yes}\\hline Complement& yes & \text{yes}&\text{no}&\text{yes}&\text{yes}&\text{no}\\hline Homomorphism& yes & \text{no}&\text{yes}&\text{no}&\text{no}&\text{yes}\\hline $ϵ$-free Substitution& yes & \text{no}&\text{yes}&\text{yes}&\text{no}&\text{yes}\\hline \end{tabular} \end{table} \chapter{Complexity Theory} \section{The Class P} {\bfseries [Informal:]}\par [practical feasibility of algorithms through deterministic variants]\par {\bfseries [Formal:]}\par [a TM is said to be PB if there is a $p(|w|)$ that, for any input $w$, there is no $C$ such that] $[\left[(s,\Delta \underline{\#}w){⊢}_M^{p(|w|)+1}C\right]:M\times \le p(|w|)]$ $\left[P=\{"M""w":M\times \le |w{|}^2\}\right]$ \section{Higher Classes} [extricate constraints] \begin{enumerate} \item {[The Class EXP]} $[\left[(s,\Delta \underline{\#}w){⊢}_M^{p^{(|w|)}+1}C\right]:M\times \le p^{(|w|)}]$ $\left[E=\{"M""w":M\times \le 2^{|w|}\}\right]$ \item {[The Class NP]} $[\left[(s,\Delta \underline{\#}w){⊢}_{NM}^{p(|w|)+1}C\right]:NM\times \le p^{(|w|)}]$ $\left[NP=\{"NM""w":NM\times \le {|w|}^2\}\right]$ \end{enumerate} \section{NP-completeness} [a lang $L$ is a NP-complete if $L\in NP$ such that for every $L^{\prime }\in NP$, there is a polyred from $L^{\prime }$ to $L$] $[P=NP\leftrightarrow L_{\text{NP}}\in P]$ \section{Automatas Algorithms} \begin{enumerate} \item {[Finite Automatas]} $[w\in L:O(|w|),w\in L:O(K^2|w|)]$ $[P:\text{min}(DFA),RE\to NDFA,DF{A}_1\sim DF{A}_2]$ $[NP:NDFA\to DFA,NDFA\to RE,NDF{A}_1\sim NDF{A}_2]$ \item {[Pushdown Automatas]} $[P:CFG\to PDA,PDA\to CFG,w\in L(G)]$ \end{enumerate}