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