Source

course-sjsu-cs154 / 02-01-2012.md

Full commit

Notes February 1, 2012

Doing Chapter 3.1 after 2.1, then 2.2, 2.3, 2.4, 3.2..

"Mapping between 1 and λ the cause of some amusement down the road"

Theorem 5: x^m x^n = x^(m+n)

Proof by induction on n

Basis: If n = 0 then x^n is λ so that x^mx^n = x^m. But also that x^m+n x^m.

Induction step: If n > 0 then x^n = x^n = x^(n-1)x so

    x^mx^n = x^m(x^(n-1)x)
    = x^mx^(n-1)x [by the previous theorem]
    = (x^(m+n-1))x [by induction]
    = x^(m+n)

Corollary x^m = xx^(m-1)

Theorem 6: (L*)* = L*

L* = U^(∞)_(k=0) L^k

Proof to show two containments. One direction is easy, L* = (L*)^1 is a subset of (L*)*j. To show that (L*)* is a subset of L*, we need to show that (L*)^n is a subset of L* for every n. This can be done by induction on n.

Bases: if n=0, then (L*)^0 = {λ}, which is clearly a subset of L*.

Inductive step: If n > 0, then (L*)^n = (L*)^(n-1)L*.

So for any x in L*)^n, x = yz where y is in L*^(n-1) and z is in L*.

By induction y is in L*. So y is in L^k for some k., But now x is in L^k+1, so x is in L*.

String Reversal

What does it mean to reverse the string w?

  • w = λ if w = λ
  • az^R if w = za

So for example:

    (abc)^R = c(ab)R
    = c(b(a^R)
    = cba

Uses of DFAs

Given an input string, as whether it's a legal identifier in some language.

Recognizing legal identifiers and literals.

  • strings beginning with a letter followed by some digits
  • strings consisting only of letters
  • strings that contain at most one digit

A DFA is an abstraction of a machine that is tailored to a particular question.

Represents an {algorithm,program,type of algorithm} rather than computers.

An abstract machine for a simple siwtch.

An abstraction of a lightswitch has two states, on and off. Transitions are possible between states. It would need to be clear which was the initial state. This information can be summarized in a diagram:

-> (on)<--> ((off))

this machine is not yet a DFA since it has nothing to do with languages.

By labelling transitions with symbols from the alphabet, we'd get a DFA.

If we label both transitions with a -, the resulting DFA would correspond to the set of strings of odd length over alphabet {0}.

A deterministic finite acceptor (automaton) consists of:

  • A finite input alphabet Σ
  • A finite set Q of states
  • An initial or start state q0
  • A set F of final states (A subset of Q)
  • A transition function δ:QxΣ -> Q

Note that both the alphabet and set of states are finite, a DFA has a finite description.

  • delta may be extended to handle strings.
  • this gives a function delta: Q x E -> Q deltastar is defined for a ll states q, strings w and symbols a by