⚛️

# Theory of Computation

Tags Computer scienceMathScience @January 12, 2022 6:58 PM @July 10, 2022 6:28 PM

# Resources

#### History

NameTags
Machines, Languages, and Computation at MITPeter J. DenningTheoretical Models of Computationanecdotes

# Strings and Languages

## Definitions.

Alphabet. Any non-empty finite set. We generally use either capital Greek letters $\Sigma ,\Gamma$﻿ , or uppercase letters $A,B,...$﻿ to designate alphabets.

Symbol. The members of an Alphabet.

Examples: $\Sigma_1=\{0,1\};\Sigma_2=\{a,b,c,d,e,f,g,h\};\Gamma=\{0,1,x,y,z\}$﻿

String over an alphabet. A finite sequence of symbols from that alphabet.

Length of a string. If $w$﻿ is a string over $\Sigma$﻿, the length of $w$﻿, written $|w|$﻿, is the number of symbols that it contains. Some authors prefer to use $n_a(w)$﻿ for indicating some $a$﻿ characteristic applied on $w$﻿.

Empty string. $|w|=\epsilon=\lambda=0$﻿

Language. Set of strings. We generally use upper-case letters $A,B,...$﻿ to designate languages.

Lexicographic ordering.

1. Shorter strings precede longer strings.

2. The first symbol in the alphabet precedes the next symbol.

## Regular operations.

Let $A,B$﻿ be languages:

Union: $A\cup B=\{w|w\in A\text{ or }w\in B\}$﻿

Concatenation: $A\cdot B=\{xy|x\in A\text{ or }y\in B\}=AB$﻿

$A^k=A \overset{\text{k times}}{ A...A},A^1=A,A^0=\{\epsilon\}$﻿

Kleene star: $A^*=\{x_1...x_k|\text{ each }x_i\in A \text{ for } k\ge 0\}=A^0\cup A^1\cup A^2 \cup A^3 \cup...$﻿, note $\epsilon\in A^*$﻿ always.

Kleene plus: $A^+=A^1\cup A^2\cup A^3\cup...=V^*V$﻿

Example. Let $A=\{good,bad\}$﻿ and $B=\{boy,girl\}$﻿

$A\cup B=\{good,bad,boy,girl\}$﻿

$AB=\{goodboy,goodgirl,badboy,badgirl\}$﻿

$A^2=\{goodgood,goodbad,badgood,badbad\}$﻿

$A^*=\{\epsilon,good,bad,goodgood,bgoodbad,badgood,badbad,goodgood,good,goodgoodbad,...\}$﻿

Homework

# Models of computation

https://cs.brown.edu/people/jsavage/book/pdfs/ModelsOfComputation_Chapter4.pdf

# Grammar

Interpreter

Formal grammar is a tool for syntax, not semantics.

## Vocabulary

Grammar. A grammar is a 4-tuple $(V,T,S,P) ,$﻿

where $V$﻿ is a finite set of objects called variables,

$T$﻿ is a finite set of objects, disjoint from $V$﻿, called terminal symbols, in short terminals,

$S\in V$﻿ is a special symbol called the start variable,

$P$﻿ is a finite set of rules, called production rules, with each rule being a variable a string of variables and terminals.

BNF. A particular form of notation for grammar (Backus-Naur form).

CNF. A particular form of notation for grammar (Chomsky normal form).

Language generated by $G$﻿. Let $G=(V,T,S,P) ,$﻿ be a grammar. Then the set

is the language generated by G.

Production rules. If production rules are of the form

where $x \in (V \cup T)^+$﻿, $y \in (V \cup T)^*$﻿. The production rules are applied in the following manner: Given a string $w_1=uxv$﻿

 Rule Application Result @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$x \to y$﻿ @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$w_1=u\bold{x}v$﻿ @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$w_2=u\bold{y}v$﻿

We say that $w_1$﻿ derives $w_2$﻿ o that $w_2$﻿ is derived from $w_1$﻿.

A rule can be used whenever it’s applicable.

If $w_1\to w_2\to ...\to w_n,$﻿

we say that $w_1$﻿ derives $w_n$﻿ and write

$w_1 \to^* w_n$﻿. The * indicates an unspecified number of steps (including zero).

## Chomsky normal form (CNF) example

$V=\{P,S,M\}$﻿, $T=\{+,*,1,2,3,4\}$﻿, $S\in V$﻿

## Backus–Naur form (BNF) example

$V=\{P,S,M\}$﻿, $T=\{+,*,1,2,3,4\}$﻿, $S\in V$﻿

## Grammar Hierarchy

### Table view

 Grammar type Grammar accepted Language Accepted Automaton Production rule form Type 0. These are the most general. Free or unrestricted grammars Recursively enumerable language Turing Machine @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$u\to v$﻿, where both u and v are arbitrary strings of symbols in V, with u non-null. Type 1 Context-sensitive grammars Context-sensitive language Linear-bounded automaton @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$uXw\to uvw,$﻿ where @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$u$﻿,@import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$v$﻿, and @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$w$﻿ are arbitrary strings of symbols in @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$V$﻿, with @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$v$﻿ non-null, and @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$X$﻿ a single nonterminal. In other words, in a particular context. Type 2 Context-free grammars Context-free language Pushdown automaton @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$X\to v$﻿, where @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$v$﻿ is an arbitrary string of symbols in @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$V$﻿, and @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$X$﻿ is a single nonterminal. i.e. regardless of context. Type 3. These grammars are the most limited in terms of expressive power. Regular grammars Regular language Finite-state automaton @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$X \to a$﻿, @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$X \to aY$﻿ (right-regular grammar), @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$X \to Ya$﻿ (left-regular grammar), @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$X \to \epsilon$﻿, where @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$X$﻿ and @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$Y$﻿ are nonterminals and @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$a$﻿ is a terminal. Regular grammar is either right-linear grammar or left-linear grammar, but not both. Mixing left-regular and right-regular rules are the context-free grammar.

https://www.cs.utexas.edu/users/novak/cs343283.html

# Classification

• Acceptors
• Transducers
• Generators (also called sequencers)

## Steps to convert regular expressions directly to regular grammars and vice versa

https://cs.stackexchange.com/questions/68575/steps-to-convert-regular-expressions-directly-to-regular-grammars-and-vice-versa

# FAQ

Are axioms in math equivalent to production rules in unrestricted grammars?

how could a CFG hold an unrestricted grammar (UG), which is turing complete?

https://stackoverflow.com/questions/61952877/chomsky-hierarchy-examples-with-real-languages?rq=1

## Notes and references

[1] M. Johnson, “Formal Grammars Handout written,” 2012 [Online]. Available: https://web.stanford.edu/class/archive/cs/cs143/cs143.1128/handouts/080 Formal Grammars.pdf. [Accessed: 28-Feb-2022]

# Finite automata

Finite automata and their probabilistic counterpart Markov chains. Finite Automaton (FA) or Finite-State Machine. An automaton (Automata in plural).

• The computer is complex, instead, we use an idealized computer called a computational model.
• A finite automaton:

We feed the input string $01$﻿ to the machine $M_1$﻿, the processing proceeds as follows:

1. Start in state $q_1$﻿.
1. Read 1, follow the transition from $q_1$﻿ to $q_2$﻿.
1. Read 1, follow the transition from $q_2$﻿ to $q_1$﻿.
1. Accept because $M_1$﻿ is in an accept state $q_2$﻿ at the end of the input.

## The formal definition of a deterministic finite automaton (DFA)

A finite automaton is a 5-tuple $(Q,\Sigma,\delta,q_0,F)$﻿ where

1. $Q$﻿ is a finite set called the states,
1. $\Sigma$﻿ is a finite set called the alphabet,
1. $\delta:Q\times \Sigma\rarr Q$﻿ is the transition function,
1. $q_0 \in Q$﻿ is the start state, and
1. $F\subseteq Q$﻿ is the set accept states, they are sometimes called final states.

## The formal definition of a nondeterministic finite automaton (NFA)

A finite automaton is a 5-tuple $(Q,\Sigma,\delta,q_0,F)$﻿ where

1. $Q$﻿ is a finite set called the states,
1. $\Sigma$﻿ is a finite set called the alphabet,
1. $\delta:Q\times (\Sigma\cup\{\lambda\})\rarr P(Q)=\{R|R \subseteq Q\}$﻿ is the transition function (P is a power set),
1. $q_0 \in Q$﻿ is the start state, and
1. $F\subseteq Q$﻿ is the set accept states, they are sometimes called final states.

## Converting NFAs to DFAs

delta = {
'state1': {
'symbol1': {'state1', 'state2',...}
}
}
# BFS
NFAToDFA(NFA)



## FAQ

What is the difference between finite automata and finite state machines?

Pattern Matching

Extended finite-state machine

https://www.seas.upenn.edu/~lee/10cis541/lecs/EFSM-Code-Generation-v4-1x2.pdf

# Regular expressions to Automata

1. Generalized nondeterministic finite automaton.
def convert_to_regular_rxpression(G):
if G.number_of_states == 2:
return 
1. Solving right-linear equation by Arden’s rule.