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.
Automata and Languages
Context-Free Languages
Church-Turing Thesis
Decidability
Undecidability
Relationships
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.
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_{0}, F) where
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:
- 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_{0}, F) where
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:
- 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_{start}, q_{accept}) where
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 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_{0}, F) where Q, Σ, Γ, and F are all finite sets and
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.
- 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_{0}, F) where Q, Σ, Γ, and F are all finite sets and
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 ∅
- 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_{0}, q_{accept}, q_{reject}) where Q, Σ, Γ are all finite sets and:
A Turing machine M accepts input w if a sequence of configurations C_{1},C_{2},...,C_{k} exists, where:
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.
- 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_{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) }
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_{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) = Σ* }
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
← October 2020 →
S | M | T | W | T | F | S |
---|---|---|---|---|---|---|
1 | 2 | 3 | ||||
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 | 31 |
Tags
My Blog Links
Recent Entries
Recent Comments
Search My Blog
0 user(s) viewing
0 Guests
0 member(s)
0 anonymous member(s)
0 member(s)
0 anonymous member(s)