CSCE 222 Lecture 26

« previous | Friday, April 8, 2011 | next »

Merge-Sort

Recurrence relation of:

$M(n)=2M\left({\tfrac {n}{2}}\right)+n$

By comparing to the general Master Theorem function, $a=2=b^{d}$, so $M(n)=O(n\log {n})$

Multiplication

(From previous lecture)

$K(n)=3K\left({\tfrac {n}{2}}\right)+Cn$

• $a=3$
• $b^{d}=2^{1}$
• $a>b^{d}$

Therefore, $K(n)=O(n^{\log _{2}{3}})$

Chapter 12: Modeling Computation

Formal Languages

alphabet (vocabulary)

a finite non-empty set of certain symbols

If $V$ represents our alphabet, $V^{*}$ represents the set of all words over $V$

word (sentence)

a string of finite length over an alphabet/vocabulary

empty string represented by λ (some books use ε)

grammar

a 4-tuple $G=(V,T,S,P)$ that consists of:

• an alphabet $V$
• terminal symbols or keywords $T$ (a subset of $V$)
• a start symbol $S$ (a symbol in $V$)
• a finite set of productions $P$

$N=V-T$ is a set of all non-terminal symbols.

Note: terminal symbols will never occur on the left hand side.

⇒ represents that a single rule is applied to the left-hand side to produce the right-hand side (1-step)

⇒* represents that multiple rules are applied to the left-hand side to produce the right-hand side (n-step)

language

a set of a grammar such that a start symbol can be converted into a terminal symbol in any number of steps

$L(g)=\{w\in T^{*}~|~S\Rightarrow ^{*}w\}$

Example 1

$G=(V,T,S,P)$

• $V=\{a,b,A,B,S\}$
• $T=\{a,b\}$
• $S$ is start symbol
• $P=\{S\rightarrow ^{1}ABa,\ A\rightarrow ^{2}BB,\ B\rightarrow ^{3}ab,\ AB\rightarrow ^{4}b\}$

What kind of words can we generate with this grammar?

1. Start out with S (start symbol)
2. Use any rules in P with S on the left-hand side
3. Choose any production rule that matches any set of symbols that were returned by the previous step
4. Once we are left with terminal symbols, nothing more can be produced by those letters

S ⇒¹ ABa ⇒² BBBa ⇒^{3 × 3} abababa

Example 2

$G=(V,T,S,P)$

• $V=\{S,A,a,b\}$
• $T=\{a,b\}$
• $P=\{S\rightarrow aA,\ S\rightarrow b,\ A\rightarrow ab\}$

$L(G)=\{b,aaa\}$