CS481 Fall 2001 -- Proving L = L(M)

Here is a typeset example hot off the laptop.

Here is some correspondence about this:

From: dhy3@cornell.edu
Subject: CS 481: HW 1

what's the general paradigm for formally proving that a given machine 
accepts a given language?

From: aww6@cornell.edu
To: Dennis Han Yeh 
Subject: Re: CS 481: HW 1

The general idea is to show two things:

Suppose you are trying to prove that machine M accepts language L.

1. Show that any string in L leads to a final state in M.
this implies that L(M) is at least L.

2. Show that L contains any string accepted by M.
this implies that L is at least L(M).

This way you have shown L(M) = L.

From: dhy3@cornell.edu
To: Allen Weipong Wang 
Subject: Re: CS 481: HW 1

ok, so how do you formally show that a string leads to a final state/that 
any string accepted by a machine is in a language.  induction, i imagine, 
but what will the induction look like?  is there perhaps, an example from 
the textbook or elsewhere?

From: Allen Wang 
To: dhy3@cornell.edu (Dennis Han Yeh)
Subject: Re: CS 481: HW 1

I'm not sure what Prof. Demers has in mind for the formality, but this is
what I *think* is the way to do it.

Here's a bit of explanation on how to show, for example, that a string in
some language leads to the the string being accepted by a machine.

Generally the formality will come from defining thoroughly parts of your
DFA or NFA. For example, ensure that your delta function is well defined
for transitions at every node. In most cases when your proof of regularity
for a language L is done in such a manner that involves constructing a
machine M, the language is simple enough that you can find a nice way to
represent a string in it. For example, the language consisting of all
strings starting with 2 "a"s (Sigma = {a,b}) would be easily represented as
aaw, where w is any string in Sigma.

Now what you do is apply the delta (big Delta function) to your
representative string (from L), and case-by-case strip off one character at
a time from the string and follow your transitions bit by bit. Ultimately
you'd like to make it so that the intersection of results from your (big
Delta) transition function and the set of Final states in M is not empty.
This will show that the string is accepted by M. 

*I imagine induction could potentially be used for steps in this, if the
transition function involves lots of repetitions of some sort. However it
is usually possible that you can simply follow the delta functions step by
step without needing induction.

For showing that a string in L(M) is in L, you do a very similar trace.
Begin with the fact that a string in L(M) implies that the intersection of
its Delta with F is non-null. Now you can work backwards from F, building
up a string along the way, trying to reach S. When you reach S, you want
the string you've built to be a string in L.

Having done both of these shows that L(M) = L.

(Fellow TA's, please correct me and/or add to this if you see something
wrong. Thanks.)