Testing for acceptance of Kleene closure of alphabet

From: Mark \(The WannaBe\) (mark_hsn_at_hotmail.com)
Date: 10/17/04 

Date: Sun, 17 Oct 2004 14:08:53 +0200

Hi

I have tried my best at coming up with a solution to the problem given
between the lines --#--#--.

--#--#--.
Suppose L is a regular language with alphabet SIGMA. Give an algorithm to
tell whether L = SIGMA*, i.e. all strings over its alphabet.
--#--#--.

The problem is the same as exercise 4.3.3 from "Introduction to Automata
Theory, Languages, and Computation" by Hopcroft et al.

My attempt of a solution is given below between the lines --*--*--. I
believe that my solution is correct but based on previous attempts I cannot
be so sure. I am a wannabe and that can make me walk on the wrong direction
for quite some time before me ever notice that the road ended a looong time
ago.

--*--*--
Let M be a DFA accepting L, let n be the number of states in a M, let SIGMA
be the alphabet of L, let SIGMA* be the Kleene closure of SIGMA and let
|SIGMA| be the number of symbols in the alphabet.

A language L=SIGMA* can be represented by a DFA which always accepts. For a
DFA to always accept then the following should be fulfilled: the start state
must be accepting, all the reachable states from the start state must be
accepting, and from each state there must be a transition (path) to an
accepting state for each symbol of the alphabet.

In coming up with an algorithm which can test if L=SIGMA*, then we will
assume that L is represented as a DFA named M, if L is not represented as
DFA, then we will assume that it can be converted to the form of a DFA.

To test if L=SIGMA* then we will create an algorithm testing whether M is
accepting ALL strings w from SIGMA* with a length in the range 0<=|w|<=n.
Below it is justified why it is enough to test for acceptance of ALL strings
in this range.

We have the lower bound 0, because the starting state of the DFA shall be
accepting, i.e. before M is given any input, then M shall be in an accepting
state, this is the same as M is accepting the empty string. The range and
its upper bound n are explained as follows. Let n be the number of states in
a DFA M accepting L. A requirement for the DFA M accepting SIGMA* is that
all reachable states from the start state is accepting. The longest possible
path in a DFA M with no cycles is n-1 so to test that all reachable states
in the DFA is accepting we need to make sure that M accepts strings w from
SIGMA* in the range 0<=|w|<=n-1. The final requirement is that from each
accepting state there shall be a transition, for each symbol of the
alphabet, to an accepting state. For all of the n states of M we have
|SIGMA| transitions to test, and each transition shall end in an accepting
state, to fulfil this requirement we also have to test all strings w of
length n, that makes the final ranges of string lengths to be tested
0<=|w|<=n.
--*--*--

Is this solution given above correct and clear enough to be an acceptable
solution of the problem? I haven't used any proof technique as prove by
contradiction etc. and I do not know if that would have made any difference
to my explanation above? Or should I always trying to use some kind of a
proof technique to make my point? Above I only tried to do simple reasoning
to justify what I did, but when my textbook presented a similar result then
it used proof by contradiction to make its point? I have described my
algorithm by words, actually I have only sketched the algorithm, I do not
know if that is acceptable? I know that I lost my head on a solution to an
algorithm given by my book in only words, until Rick Decker provided pseudo
code explaining how the algorithm should be read, but since my textbook
occasionally is giving only textual descriptions of algorithms I guess it is
acceptable in a solution like this?

Kind regards
Mark (The WannaWannaBe of Computer Science)

Relevant Pages

  • Re: Testing for acceptance of Kleene closure of alphabet
    ... > Dick's suggestion of leaning on the algorithm for testing emptiness is ... An alternative is leaning on the algorithm for minimizing a DFA ... > and the fact that any regular language has a unique minimal DFA. ... Let DFA A be a DFA accepting L. Let SIGMA be the alphabet of L. Let SIGMA* ...
    (comp.theory)
  • Re: ArrayList BinarySearch vs Contains
    ... So it seems that choosing an appropriate algorithm depends not only on ... notation doesn't account for such as scale, ... Quicksort is dependent on the distribution of the data and how you pick the ... or by simply ignoring the problem and accepting that occasionally you'll get ...
    (microsoft.public.dotnet.languages.csharp)