Automata: The Methods & The Madness: Angkor Wat, Cambodia

Chapter 1
Automata: the Methods & the Madness
Angkor Wat, Cambodia
(updated 2015/09/16)
1
Outline
1.1 Why Study Automata Theory?

1.2 Introduction to Formal Proof
1.3 Additional Forms of Proof
1.4 Inductive Proofs
1.5 Central Concepts of Automata Theory
2
1.1 Why Study Automata Theory?
1.1.1 Introduction to Automata
 Properties of finite-state systems ---

 Having a finite number of states
 With its running history not kept
 Good to implement with a fixed set of resources
 Easy to model by finite automata (FA)
 Example 1.1 --- an FA modeling an on/off switch (see Fig. 1.1)
push
start off on
push
Fig. 1.1 An FA modeling an on/off switch.
 Example 1.2 --- an FA modeling recognition of the keyword “then” in a lexical analyzer
 The double circles specify the “final” or “accepting” state.
t h e n
start t th the then
Fig. 1.2 an FA modeling recognition of the keyword “then.”
1.1.2 Structural Representation
 Two other models (not automaton-like) for string data representation ---
 Grammar --- processing data (strings of symbols) with recursive structures
 e.g., grammatical rule “E  E + E” for generating arithmetic expressions like “2+
2”
 Regular expression --- describing text strings

 e.g., UNIX-style regular expression ’[A-Z][a-z]*[ ][A-Z][A-Z]’ for describing
partial addresses Ithaca NY, Lafayette IN…
1.1.3 Automata and Complexity
 What can a computer do? ---

This is a question which is answered by the study of computability!
 Computability is a study of problems which can be solved by computers, called
decidable problems.
 Decidability is the main topic in the study of computability.
 What can a computer do efficiently? ---
3
This is a question which can be answered by the study of computational complexity!
 Computational complexity is a study of:
 tractable problems solvable with slowly growing functions (like polynomial) of
input size, and
 intractable problems solvable with fast growing functions (like exponential).
 Intractability is the main topic of computational complexity.
1.2 Introduction to Formal Proof
1.2.0 Concepts
 Formal proof techniques are indispensable for proving theorems in theory of computation.
 Understanding how correct programs work is equivalent to proving theorems by
induction.
1.2.1 Deductive Proofs (演繹法 )

 An illustration of deductive proof is as shown in Fig. 1.3.
 Logic principles used: modus ponens (正前律、離斷規則、肯定前件), syllogism (三段
論)…
Given facts (e.g. axioms), previous statements
Hypothesis  deduced statements  …  conclusion
Logic principles
Fig. 1.3 An illustration of deductive proof.
(Sec. 1.2.2~1.2.4 --- read by yourself)
 Modus ponens (正前律、離斷規則、肯定前件)

 An example of applying modus ponens:
“If it rains, the sidewalk will be wet.
It rains now.
So the sidewalk is wet.”
 Syllogism (三段論) (supplemental)

 An example of applying syllogism:
“All humans will die.
Socrates is a human.
So, Socrates will die.”
1.3 Additional Forms of Proof
1.3.0 Some More Proof Techniques

 Proofs about sets
 Proofs by contradiction
4
 Proofs by counterexamples
(1.3.1~1.3.4 --- read by yourself)
1.4 Inductive Proofs (歸納法)
1.4.1 Induction on Integers

 To prove a statement S(n) about an integer n by induction, we do:
 Basis --- show S(i) true for a particular basis integer i (0 or 1 usually)
 Inductive step --- assume n  i (basis integer), and show that the statement “if S(n),
then S(n + 1)” is true.
(1.4.2~1.4.4 --- read by yourself)
1.5 Central Concepts of Automata Theory
1.5.0 Three basic concepts

 Alphabet --- a set of symbols
 Strings --- a sequence of symbols from an alphabet
 Language --- a set of strings from the same alphabet
1.5.1 Alphabets
 Definition ---
An alphabet is a finite, nonempty set of symbols.
 Conventional notation --- 
 The term “symbol” is usually undefined.
 Examples ---
 Binary alphabet  = {0, 1}
 English alphabet = {a, b, …, z} …
1.5.2 Strings
 Definition ---
A string (or word) is a finite sequence of symbols from an alphabet.
 An example --- 1011 is a string from the binary alphabet  = {0, 1}.
 Empty string  --- a string with zero occurrences of symbols.
 Length |w| of string w --- the number of positions for symbols in w

 Examples --- |0111| = 4, || = 0, …
 Power of a symbol a ---

The kth power ak of a is the result of concatenating a for k times, i.e.,
ak = aa…a (k times).
 Power of an alphabet  ---

The kth power of , k is a set of all strings of length k.
 Examples --- given  = {0, 1}, we have
 0 = {}, 2 = {00, 01, 10, 11}

5
 Power of a string x (supplemental) ---
 Defined by concatenation ---
xi = xx…x (x concatenated i times)
 Defined by recursion ---
(1) x0 =  (by definition); and
(2) xi = xxi-1
 Examples --- (10)0 = , (011)2 = 011011…
 Note --- for a symbol a, we define a0 =  (i.e., in this case we regard a as a one-symbol
string).
 Set of all strings over  --- denoted as 

 It is not difficult to know that  = ∪1∪2∪…
 + = the set of nonempty strings from  = *  {}

 Therefore, we have
 = ∪2∪3∪…
* = +∪{}
 Concatenation of two strings x and y --- xy

 Examples ---
if x = 01101, y = 110, then xy = 01101110, xx = x2 = 0110101101, …
  is the identity for concatenation since w = w = w.
1.5.3 Languages
 Definition ---
A language is a set of strings all chosen from some *.
 In other words:
if  is an alphabet, and L*, then L is a language over .
 Examples ---
 The set of all legal English words is a language.
 Why? What is the alphabet here?
Answer: the set of all letters.
 A legal program of C is a language.
 Why? What is the alphabet here?
Answer: a subset of the ASCII characters.
 More examples of languages ---

 The set of all strings of n 0’s followed by n 1’s for n  0: {, 01, 0011, 000111, …}
 * is an infinite language for any alphabet .
  denotes the empty language (not the empty string ) which is a language over any
alphabet.
 {} is a language over any alphabet (consisting of only one string, the empty string ).
 Ways to describe languages ---

 Description by exhaustive listing ---
 L1 = {a, ab, abc} (finite language; listed one by one)
 L2 = {a, ab, abb, abbb, ...} (infinite language; listed partially)
 L3 = L(ab*) (infinite language; expressed by a regular expression)
6
 Description by generic elements ---
 L4 = {x | x is over V = {a, b}, begins with a, followed by any number of b, possible
none}
 Note: L4 = L3 = L2
 Description by integer parameters ---
 L5 = {abn | n  0}
 Note: L5 = L4 = L3 = L2
1.5.3a Operations on Languages (supplemental)

 Languages are sets, and operations of sets may be applied to them:
(1) union --- A∪B = {a | a  A or a  B}
(2) intersection --- A∩B = {a | a  A and a B}
(3) difference --- A  B = {a | a  A and a  B}
(4) product --- A  B = {(a, b) | a  A and b  B}
(5) complement --- Ā = {a | a  U and a  A}
(6) power set --- 2A = {B | B  A}
 Note: U above is the universal set, just like * which is the closure of an alphabet
(defined later)
1.5.3b More Operations on Languages (supplemental)

 Concatenation of two languages L1 and L2 ---
L1L2 = {x1x2 | x1  L1 and x2  L2}
 Power of a language L ---

 Defined directly ---
Lk = {x1x2…xk | x1, x2, …, xk  L}
 Defined by recursion ---
(1) L0 = {}; and
(2) Li = LLi-1
 Closure of language L ---

�
L* = ULi = L0∪L1∪L2∪…
i =0
 Positive closure of a language L ---
L+ = L1∪L2∪…
 Note: L*  L0 = L* – }
1.5.4 Problems
 A problem in automata theory ---
deciding whether a given string is a member of some particular language.
 That is, if  is an alphabet, and L is a language over , the problem L is:

given a string w in *, decide if w  L or not.
 The solution will be studied later in the topic of decidability.

Automata: The Methods & The Madness: Angkor Wat, Cambodia

Uploaded by

Copyright:

Available Formats

Automata: The Methods & The Madness: Angkor Wat, Cambodia

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Automata: The Methods & The Madness: Angkor Wat, Cambodia

Uploaded by

Copyright:

Available Formats

Chapter 1

Automata: the Methods & the Madness

Angkor Wat, Cambodia

1.1 Why Study Automata Theory?

1.1.1 Introduction to Automata

 Properties of finite-state systems ---

 Example 1.1 --- an FA modeling an on/off switch (see Fig. 1.1)

Fig. 1.1 An FA modeling an on/off switch.

Fig. 1.2 an FA modeling recognition of the keyword “then.”

1.1.2 Structural Representation

 Regular expression --- describing text strings

1.1.3 Automata and Complexity

 What can a computer do? ---

 What can a computer do efficiently? ---

1.2 Introduction to Formal Proof

1.2.1 Deductive Proofs (演繹法 )

Given facts (e.g. axioms), previous statements

Hypothesis  deduced statements  …  conclusion

Fig. 1.3 An illustration of deductive proof.

(Sec. 1.2.2~1.2.4 --- read by yourself)

 Modus ponens (正前律、離斷規則、肯定前件)

 Syllogism (三段論) (supplemental)

1.3 Additional Forms of Proof

1.3.0 Some More Proof Techniques

(1.3.1~1.3.4 --- read by yourself)

1.4 Inductive Proofs (歸納法)

1.4.1 Induction on Integers

(1.4.2~1.4.4 --- read by yourself)

1.5 Central Concepts of Automata Theory

1.5.0 Three basic concepts

 Empty string  --- a string with zero occurrences of symbols.

 Length |w| of string w --- the number of positions for symbols in w

 Power of a symbol a ---

 Power of an alphabet  ---

 Set of all strings over  --- denoted as 

 + = the set of nonempty strings from  = *  {}

 Concatenation of two strings x and y --- xy

 More examples of languages ---

 Ways to describe languages ---

1.5.3a Operations on Languages (supplemental)

1.5.3b More Operations on Languages (supplemental)

 Power of a language L ---

 Closure of language L ---

 That is, if  is an alphabet, and L is a language over , the problem L is:

 The solution will be studied later in the topic of decidability.

You might also like