Subscribe to MentalFloss Minutes        RSS Feed
-----

Theory of Computation (TOC): Introduction

Icon Leave Comment
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

Finite Automaton said:

A finite automaton is a 5-tuple (Q, Σ, 𝛿, q0, F) where
  • Q is a finite set called the states.
  • Σ is a finite set called the alphabet.
  • 𝛿: Q x Σ → Q is the transition function.
  • q0 ∈ Q is the start state.
  • F ⊆ Q is the set of accept states.


Let M = (Q, Σ, 𝛿, q0, F) be a finite automaton and let w = w1w2...wn be a string where each wi is a member of the alphabet Σ. Then M accepts w if a sequence of states r0,r1,...,rn in Q exists with three conditions:
  • r0=q0
  • 𝛿(ri,wi+1)=ri+1, for i = 0,...,n-1
  • rn ∈ F


Nondeterministic Finite Automaton said:

A nondeterministic finite automaton is a 5-tuple (Q, Σ, 𝛿, q0, F) where
  • Q is a finite set called the states.
  • Σ is a finite set called the alphabet.
  • 𝛿: Q x Σε → 𝒫(Q) is the transition function.
  • q0 ∈ Q is the start state.
  • F ⊆ Q is the set of accept states.


Let N = (Q, Σ, 𝛿, q0, F) be an NFA and w a string over alphabet Σ. Then we say that N accepts w if we can write w as w = y1y2...ym, where each yi is a member of Σε and a sequence of states r0,r1,...,rm exists in Q with three conditions:
  • r0=q0
  • ri+1 ∈ 𝛿(ri, yi+1), for i = 0,...,m-1
  • rm ∈ F


Regular Operations said:

Let A and B be languages. We define the regular operations union, concatenation, and star as follows:
  • Union: A ∪ B = { x | x ∈ A or x ∈ B }
  • Concatenation: A ∘ B = { xy | x ∈ A and y ∈ B }
  • Star: A* = { x1x2...xk | k > 0 and each xi ∈ 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, Σ, 𝛿, qstart, qaccept) where
  • Q is a finite set called the states.
  • Σ is a finite set called the alphabet.
  • 𝛿: (Q - {qaccept}) x (Q - {qstart}) → R
  • qstart is the start state.
  • qaccept is the accept state.


A GNFA accepts a string w in Σ* if w = w1w2...wk, where each wi is in Σ* and a sequence of states q0,q1,...,qk exists such that:
  • q0=qstart
  • qk=qaccept is the accept state
  • for each i, we have wi ∈ L(Ri), where Ri = 𝛿(qi-1,qi)


Regular Expression said:

Say that R is a regular expression if R is
  • a for some a in the alphabet Σ
  • ε

  • (R1 ∪ R2) where R1 and R2 are regular expressions.
  • (R1 ∘ R2) where R1 and R2 are regular expressions.
  • (R1*) where R1 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:
  • for each i > 0, xyiz ∈ 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
  • 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.


Pushdown Automaton said:

A pushdown automaton is a 6-tuple (Q, Σ, Γ, 𝛿, q0, 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
  • q0 ∈ Q is the start state.
  • F ⊆ Q is the set of accept states.


A pushdown automaton M = (Q, Σ, Γ, 𝛿, q0, F) computes as follows. It accepts input w if w can be written as w = w1w2...wm, where each wi ∈ Σε and sequence of states r0,r1,...,rm ∈ Q and strings s0,s1,...,sm ∈ Γ* exist that satisfy the following three conditions. The strings si represent the sequence of stack contents that M has on the accepting branch of the computation.
  • r0=q0 and s0
  • for i = 0,...,m-1, we have (ri+1,b) ∈ 𝛿(ri,wi+1,a), where si=at and si+1=bt for some a,b ∈ Γε and t ∈ Γ*
  • rm ∈ F


Deterministic Pushdown Automaton said:

A deterministic pushdown automaton is a 6-tuple (Q, Σ, Γ, 𝛿, q0, 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
  • q0 ∈ 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:
  • for each i > 0, uvixyiz ∈ 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, Σ, Γ, 𝛿, q0, qaccept, qreject) 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
  • q0 ∈ Q is the start state.
  • qaccept ∈ Q is the accept state
  • qreject ∈ Q is the reject state where qaccept ≠ qreject


A Turing machine M accepts input w if a sequence of configurations C1,C2,...,Ck exists, where:
  • C1 is the start configuration of M on input w.
  • each Ci yields Ci+1
  • Ck 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:

ADFA = { ⟨ B, w ⟩ | B is a DFA that accepts input string w }
ANFA = { ⟨ B, w ⟩ | B is an NFA that accepts input string w }
AREX = { ⟨ R, w ⟩ | R is a regular expression that generates string w }
ACFG = { ⟨ G, w ⟩ | G is a CFG that generates string w }

EDFA = { ⟨ A ⟩ | A is a DFA and L(A) = ∅ }
ECFG = { ⟨ G ⟩ | G is a CFG and L(G) = ∅ }

EQDFA = { ⟨ A, B ⟩ | A and B are DFAs and L(A) = L(B) }
EQCFG = { ⟨ G, H ⟩ | G and H are CFGs and L(G) = L(H) }



Undecidability

Classifications said:

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

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

EQTM = { ⟨ M1, M2 ⟩ | M1 and M2 are TMs and L(M1) = L(M2) }

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

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

ALLCFG = { ⟨ 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

 

December 2018

S M T W T F S
      1
2345678
9101112131415
1617 18 19202122
23242526272829
3031     

Tags

    Recent Entries

    Recent Comments

    Search My Blog

    0 user(s) viewing

    0 Guests
    0 member(s)
    0 anonymous member(s)