Loading...

Chapter 1: Background and Introduction ● Theory of computers Study of mathematical models ◆ Abstract ◆ Simplify ◆ Codify (relate in a meaningful way to the physical world)

● Computability

2

● Basic questions What do theoretical models of a computer look like? What can we compute and what can’t we compute with today’s computers as well as computers of the future? Why? ● We study some precise answers. In particular, we formulate precise questions with mathematical statements and rigorous proofs.

3

History ● ● ● ●

Cantor (1845-1918) theory of sets Hilbert (1862-1943) methodology for finding proofs Gödel (1906-1978) Incompleteness theorem Church, Kleene, Post, Markov, von Neumann, Turing Which statements have proofs? building blocks of mathematical algorithms ● Turing (1912-1954) Universal machine and its limitations ● McCulloch, Pitts Neural nets (similar but with different limitations) ● Chomsky mathematical models for the description of languages 4

p. 434

I.

Language Defined by

Corresponding Accepting Machine

Language NondeterClosed minism= Determinism Under

What Can Be Decided?

Examples of Applications

Regular expression

Finite automaton, transition graph

Yes

Union, product, Kleene star, intersection, complement

Equivalence, emptiness, finiteness, membership

Text editors, sequential circuits, verification

Context-free grammar

Pushdown automaton

No

Union, product, Kleene star

Emptiness, finiteness, membership

Parsing, compilers

Type 0 grammar

Turing machine, Post machine, Pushdown automaton

Yes

Union, product, Kleene star

Not much

Computers

II.

III.

5

Chapter 2: Languages ● Mathematical models of computers Analysis of the input language ◆ Study their limitations

● Definitions alphabet – a finite set of symbols, denoted Σ letter – an element of an alphabet Σ word – a finite sequence of letters from the alphabet Σ Λ (empty string) – a word without letters language – a set of words formed from the alphabet Σ

6

Two Examples English-Words

English-Sentences

alphabet

Σ={a,b,c,d,…}

Γ=words in dictionary + space + punctuation marks

letter

letter

word

word

word

sentence

language

all the words in the dictionary

all English sentences

7

2 ways to define languages a list of all the words a set of rules (grammar) The alphabet is always finite. The set of words can be infinite. Syntax, not semantics What kind of rules are permitted? It must be possible in finite time to determine if a word is in a language or not. (algorithm) 8

● Example L1:

Σ={x}

L1={x, xx, xxx, xxxx,…} or L1={xn | n=1, 2, 3,…}

● Definition: concatenation – two words written down side by side. A new word is formed. a=xx b=xxx ab=xxxxx factor – one of the two words in a concatenation xx|xxx ● Example L2: Σ={0, 1, 2, 3, 4, 5, 6, 7, 8, 9} L2={words that do not start with the letter 0} 9

● Definition: length – number of letters in a word length(xxxxx) = 5 length(1025)=4 length(Λ)=0 reverse reverse(xxx)=xxx reverse(157)=751 ● Example PALINDROME: Σ={a, b} PALINDROME:={Λ and x|reverse(x) = x} 10

Kleene Closure ● Definition: closure of an alphabet Σ, Kleene star Given an alphabet Σ, the closure of Σ (or Kleene star), denoted Σ*, is the language containing all words made up of finite sequences of letters from Σ, including the empty string Λ. ● Examples: Σ = {x} Σ = {0, 1} Σ = {a, b, c}

Σ* = {Λ, x, xx, xxx, …} Σ* = {Λ, 0, 1, 00, 01, 10, 11, 000, 001, …} Σ* = ?

11

● Definition: closure or Kleene star of a set of words (or a language) Let S be a set of words. S* is the language formed by concatenating words from S, including the empty string Λ. ● Examples: S = {a, ab} S* = {Λ, a, aa, ab, aaa, aab, aba, aaaa, …} abaaababa ∈ S* ab|a|a|ab|ab|a factors S* = {Λ plus all sequences of a’s and b’s except those that start with b and those that contain a double b} Is the factoring always unique? 12

A Factoring that is not Unique S = {xx, xxx} xxxxxxx ∈ S* xx|xx|xxx

xx|xxx|xx

xxx|xx|xx

S* = {Λ and all sequences of more than one x}

13

● Example:

Σ=φ

Σ* = {Λ}

● The Kleene closure of an alphabet Σ always produces an infinite language unless Σ is empty. ● Example: S = {a, b, ab} S* = T* ab|a|a|ab|ab|a a|b|a|a|a|b|a|b|a

T = {a, b, bb}

● The Kleene closure of a language S always produces an infinite language unless S = φ or S = {Λ}. In this case, S* = {Λ}. 14

Positive Closure ● Definition: S+, Σ+ The language with all concatenations that contain at least 1 word from S 1 letter from Σ (S* possibly without Λ) If Λ is a member of S, S* = S+. ● Examples: Σ = {x} Σ+ = {x, xx, xxx, …} S = {aa, bbb, Λ} S+ = {aa, bbb, Λ, aaaa, aabbb, …} (N.B. aΛ = a) 15

● Theorem 1: For any set of words S, we have S**=S*. ● Definitions: equality of sets S = T: S ⊂ T and T ⊂ S subsets S ⊂ T: for all x in S, x is also in T ● Example: S = {a,b} aaba, baaa, aaba ∈S* aaba|baaa|aaba ∈S** a|a|b|a|b|a|a|a|a|a|b|a ∈S* 16

● Theorem 1: S**=S* ● Proof: Case 1: S** ⊂ S* Every word in S** is made up of factors from S* (definition of Kleene star). Every word in S* is made up of factors from S. Therefore, every word in S** is also a word in S*. Thus S** ⊂ S*. Case 2: S* ⊂ S** For any set A, we can show that A ⊂ A*. Let w be a word in A. Then w is certainly in A*. If we consider S* as our set A, we can conclude S* ⊂ S**. By definition of equality of sets, we have S* = S**. 17

Loading...