MATH 302 Lecture 24

« previous | Monday, November 28, 2011 | next »

Equivalence Classes

Interesting example:

$A=\{(p,q)|p,q\in \mathbb {Z} ,q\neq 0\}$

$R((p,q),(p',q')$ iff $pq'=p'q$

describes the classes of fraction in LCD form.

Formal Languages

Phrase Structure Grammar

• V = vocabulary/alphabet
  • T = terminal symbols (⊆ V)
  • S = start symbol (∈ V)
• V* = words/strings
  • L(G) ⊆ V*
• P = productions (rules of derivation)
• G = grammar: G(V, T, S, P)

Example

V = {a, b, A, B, S}

P = S -> ABa

   A  -> BB
   B  -> ab
   AB -> b

L(G(V, {a, b}, S, P)) = {ba, abababa}

Grammar Hierarchy

• Type 0: unrestricted
• Type 1: context-sensitive (productions are l, non-terminal, R → l, any combination of terminal and non-terminals, r)
• Type 2: context-free (productions are single nonterminal → any combination of terminal and non-terminals)
• Type 3: regular (productions are single nonterminal → one terminal and optionally one non-terminal)

Finite State Machines (without output)

(Deterministic Automata)

• S = states
  • s₀ = start state (∈ S)
• I = inputs
• f = transition function
• F = final states

M = (S, I, f, s₀, F)