What you do with this information is up to you. I personally see no use for most of it.

Anyway, I'm working through Introduction to the Theory of Computation (3rd) by Michael Sipser.

This is the most important information of the required sections (Ch1 to Ch 5.1), which give an introduction to the theory of computation. If something interests you, be sure to use the provided vocabulary to delve deeper into the subject.

Anyway, I'm working through Introduction to the Theory of Computation (3rd) by Michael Sipser.

**Automata and Languages**Finite Automaton said:

A finite automaton is a 5-tuple (Q, Σ, 𝛿, q

Let M = (Q, Σ, 𝛿, q

_{0}, F) where- Q is a finite set called the states.
- Σ is a finite set called the alphabet.
- 𝛿: Q x Σ → Q is the transition function.
- q
_{0}∈ Q is the start state. - F ⊆ Q is the set of accept states.

Let M = (Q, Σ, 𝛿, q

_{0}, F) be a finite automaton and let w = w_{1}w_{2}...w_{n}be a string where each w_{i}is a member of the alphabet Σ. Then M accepts w if a sequence of states r_{0},r_{1},...,r_{n}in Q exists with three conditions:- r
_{0}=q_{0} - 𝛿(r
_{i},w_{i+1})=r_{i+1}, for i = 0,...,n-1 - r
_{n}∈ F

Nondeterministic Finite Automaton said:

A nondeterministic finite automaton is a 5-tuple (Q, Σ, 𝛿, q

Let N = (Q, Σ, 𝛿, q

_{0}, F) where- Q is a finite set called the states.
- Σ is a finite set called the alphabet.
- 𝛿: Q x Σ
_{ε}→ 𝒫(Q) is the transition function. - q
_{0}∈ Q is the start state. - F ⊆ Q is the set of accept states.

Let N = (Q, Σ, 𝛿, q

_{0}, F) be an NFA and w a string over alphabet Σ. Then we say that N accepts w if we can write w as w = y_{1}y_{2}...y_{m}, where each y_{i}is a member of Σ_{ε}and a sequence of states r_{0},r_{1},...,r_{m}exists in Q with three conditions:- r
_{0}=q_{0} - r
_{i+1}∈ 𝛿(r_{i}, y_{i+1}), for i = 0,...,m-1 - r
_{m}∈ F

Regular Operations said:

Let A and B be languages. We define the regular operations union, concatenation, and star as follows:

Regular languages are closed under union, concatenation, star, intersection, complement.

- Union: A ∪ B = { x | x ∈ A or x ∈ B }
- Concatenation: A ∘ B = { xy | x ∈ A and y ∈ B }
- Star: A* = { x
_{1}x_{2}...x_{k}| k > 0 and each x_{i}∈ A }

Regular languages are closed under union, concatenation, star, intersection, complement.

Generalized Nondeterministic Finite Automaton said:

A generalized nondeterministic finite automaton is a 5-tuple (Q, Σ, 𝛿, q

A GNFA accepts a string w in Σ* if w = w

_{start}, q_{accept}) where- Q is a finite set called the states.
- Σ is a finite set called the alphabet.
- 𝛿: (Q - {q
_{accept}}) x (Q - {q_{start}}) →*R* - q
_{start}is the start state. - q
_{accept}is the accept state.

A GNFA accepts a string w in Σ* if w = w

_{1}w_{2}...w_{k}, where each w_{i}is in Σ* and a sequence of states q_{0},q_{1},...,q_{k}exists such that:- q
_{0}=q_{start} - q
_{k}=q_{accept}is the accept state - for each i, we have w
_{i}∈ L(R_{i}), where R_{i}= 𝛿(q_{i-1},q_{i})

Regular Expression said:

Say that R is a regular expression if R is

Regular expressions and finite automata are equivalent in their descriptive power.

- a for some a in the alphabet Σ
- ε
- ∅
- (R
_{1}∪ R_{2}) where R_{1}and R_{2}are regular expressions. - (R
_{1}∘ R_{2}) where R_{1}and R_{2}are regular expressions. - (R
_{1}*) where R_{1}is a regular expressions.

Regular expressions and finite automata are equivalent in their descriptive power.

Pumping Lemma for Regular Languages said:

If A is a regular language, then there is a number p (the pumping length) where if s is any string in A of length at least p, then s may be divided into three pieces, s=xyz, satisfying the following conditions:

This may be used to show that a language is not regular through proof by contradiction, but never that it is.

- for each i > 0, xy
^{i}z ∈ A - |y| > 0
- |xy| < p

This may be used to show that a language is not regular through proof by contradiction, but never that it is.

**Context-Free Languages**Context-free Grammar said:

A context-free grammar is a 4-tuple (V, Σ, R, S) where

Context-free languages are closed under union, concatenation, star. They are not closed under intersection, and complement.

- V is a finite set called the variables
- Σ is a finite set, disjoint from V, called the terminals
- R is a finite set of rules, with each rule being a variable and a string of variables and terminals.
- S ∈ V is the start variable.

Context-free languages are closed under union, concatenation, star. They are not closed under intersection, and complement.

Ambiguity said:

A string w is derived ambiguously in context-free grammar G if it has two or more different leftmost derivations. Grammar G is ambiguous if it generates some string ambiguously.

Chomsky Normal Form said:

A context-free grammar is in Chomsky normal form if every rule is of the form

A → BC

A → a

where a is any terminal, and A,B and C are any variables - except that B and C may not be the start variable. Also permitted: S → ε where S is start variable.

A → BC

A → a

where a is any terminal, and A,B and C are any variables - except that B and C may not be the start variable. Also permitted: S → ε where S is start variable.

Pushdown Automaton said:

A pushdown automaton is a 6-tuple (Q, Σ, Γ, 𝛿, q

A pushdown automaton M = (Q, Σ, Γ, 𝛿, q

_{0}, F) where Q, Σ, Γ, and F are all finite sets and- Q is the set of states
- Σ is the input alphabet
- Γ is the stack alphabet
- 𝛿: Q x Σ
_{ε}x Γ_{ε}→ 𝒫(Q x Γ_{ε}) is the transition function - q
_{0}∈ Q is the start state. - F ⊆ Q is the set of accept states.

A pushdown automaton M = (Q, Σ, Γ, 𝛿, q

_{0}, F) computes as follows. It accepts input w if w can be written as w = w_{1}w_{2}...w_{m}, where each w_{i}∈ Σ_{ε}and sequence of states r_{0},r_{1},...,r_{m}∈ Q and strings s_{0},s_{1},...,s_{m}∈ Γ* exist that satisfy the following three conditions. The strings s_{i}represent the sequence of stack contents that M has on the accepting branch of the computation.- r
_{0}=q_{0}and s_{0}=ε - for i = 0,...,m-1, we have (r
_{i+1},b) ∈ 𝛿(r_{i},w_{i+1},a), where s_{i}=at and s_{i+1}=bt for some a,b ∈ Γ_{ε}and t ∈ Γ* - r
_{m}∈ F

Deterministic Pushdown Automaton said:

A deterministic pushdown automaton is a 6-tuple (Q, Σ, Γ, 𝛿, q

The transition function 𝛿 must satisfy the following condition.

For every q ∈ Q, a ∈ Σ, and x ∈ Γ, exactly one of the values 𝛿(q,a,x), 𝛿(q,a,ε), 𝛿(q,ε,x) and 𝛿(q,ε,ε) is not ∅

_{0}, F) where Q, Σ, Γ, and F are all finite sets and- Q is the set of states
- Σ is the input alphabet
- Γ is the stack alphabet
- 𝛿: Q x Σ
_{ε}x Γ_{ε}→ (Q x Γ_{ε}) ∪ {∅} is the transition function - q
_{0}∈ Q is the start state. - F ⊆ Q is the set of accept states.

The transition function 𝛿 must satisfy the following condition.

For every q ∈ Q, a ∈ Σ, and x ∈ Γ, exactly one of the values 𝛿(q,a,x), 𝛿(q,a,ε), 𝛿(q,ε,x) and 𝛿(q,ε,ε) is not ∅

Pumping Lemma for Context-free Languages said:

If A is a context-free language, then there is a number p (the pumping length) where, if s is any string in A of length at least p, then s may be divided into five pieces s = uvxyz satisfying the following conditions:

This may be used to show that a language is not context-free through proof by contradiction, but never that it is.

- for each i > 0, uv
^{i}xy^{i}z ∈ A - |vy| > 0
- |vxy| < p

This may be used to show that a language is not context-free through proof by contradiction, but never that it is.

**Church-Turing Thesis**Turing Machine said:

A Turing machine is a 7-tuple (Q, Σ, Γ, 𝛿, q

A Turing machine M accepts input w if a sequence of configurations C

Call a language Turing-recognizable if some Turing machine recognizes it. Recognizable languages are close under same as decidable except for complement.

Call a language Turing-decidable or simply decidable if some Turing machine decides it. Decidable languages are closed under union, concatenation, star, intersection, and complement.

_{0}, q_{accept}, q_{reject}) where Q, Σ, Γ are all finite sets and:- Q is the set of states
- Σ is the input alphabet not containing the blank symbol □
- Γ is the tape alphabet, where □ ∈ Γ and Σ ⊆ Γ
- 𝛿: Q x Γ → Q x Γ x {L,R} is the transition function
- q
_{0}∈ Q is the start state. - q
_{accept}∈ Q is the accept state - q
_{reject}∈ Q is the reject state where q_{accept}≠ q_{reject}

A Turing machine M accepts input w if a sequence of configurations C

_{1},C_{2},...,C_{k}exists, where:- C
_{1}is the start configuration of M on input w. - each C
_{i}yields C_{i+1} - C
_{k}is an accepting configuration

Call a language Turing-recognizable if some Turing machine recognizes it. Recognizable languages are close under same as decidable except for complement.

Call a language Turing-decidable or simply decidable if some Turing machine decides it. Decidable languages are closed under union, concatenation, star, intersection, and complement.

**Decidability**Classifications said:

A

A

A

A

E

E

EQ

EQ

_{DFA}= { ⟨ B, w ⟩ | B is a DFA that accepts input string w }A

_{NFA}= { ⟨ B, w ⟩ | B is an NFA that accepts input string w }A

_{REX}= { ⟨ R, w ⟩ | R is a regular expression that generates string w }A

_{CFG}= { ⟨ G, w ⟩ | G is a CFG that generates string w }E

_{DFA}= { ⟨ A ⟩ | A is a DFA and L(A) = ∅ }E

_{CFG}= { ⟨ G ⟩ | G is a CFG and L(G) = ∅ }EQ

_{DFA}= { ⟨ A, B ⟩ | A and B are DFAs and L(A) = L(B) }EQ

_{CFG}= { ⟨ G, H ⟩ | G and H are CFGs and L(G) = L(H) }**Undecidability**Classifications said:

A

E

EQ

HALT

REGULAR

ALL

_{TM}= { ⟨ M, w ⟩ | M is a TM and M accepts w }E

_{TM}= { ⟨ M ⟩ | M is a TM and L(M) = ∅ }EQ

_{TM}= { ⟨ M_{1}, M_{2}⟩ | M_{1}and M_{2}are TMs and L(M_{1}) = L(M_{2}) }HALT

_{TM}= { ⟨ M, w ⟩ | M is a TM and M halts on w }REGULAR

_{TM}= { ⟨ M ⟩ | M is a TM and L(M) is a regular language }ALL

_{CFG}= { ⟨ G ⟩ | G is a CFG and L(G) = Σ* }**Relationships**Recognizable said:

Decidable said:

Context-free Language said:

Deterministic Context-free Language said:

Regular Language said:

Finite said:

Empty said:

**Conclusion**This is the most important information of the required sections (Ch1 to Ch 5.1), which give an introduction to the theory of computation. If something interests you, be sure to use the provided vocabulary to delve deeper into the subject.

### 0 Comments On This Entry

### Tags

### My Blog Links

### Recent Entries

### Recent Comments

### Search My Blog

### 1 user(s) viewing

**1**Guests

**0**member(s)

**0**anonymous member(s)