Re: The state machine of no input

briggs_at_encompasserve.org
Date: 10/06/04 

Date: 6 Oct 2004 07:12:33 -0500

In article <cjv0qb$72c$1@news.cybercity.dk>, "Mark \(The WannaBe\)" <mark_hsn@hotmail.com> writes:
> Hi
>
> I know I am already having some threads going on, but I take my chance,
> because I suddenly lost my head on this on question. I am still the Danish
> wannabe of computer science and that can be the basis for very dumb
> questions from me, but I try my best not to ask something I could have found
> out my self by reading a book or searching google. I hope this is the right
> forum to also ask a question like this and I have been really grateful for
> previous replies by William Elliot which have helped me to do some cleaning
> up in my wannabe head full of wrong views of the land of dark magic of
> computer science.
>
> I have been given a state machine, which takes no input, even though it has
> state transitions with explicit rules for each state transition. I have to
> prove a property about the language accepted by this state machine, which
> takes no input. The question says that I should treat the state machine as a
> DFA. But the state machine takes no input and each state transition is
> triggered by nothing i.e. they are triggered by the empty string. Now as far
> as I can figure out, and I am only a wannabe of computer science, then the
> only language accepted by a state machine taking no input must be the empty
> string and then only if the starting state is an accepting state.

How did your textbook define what it means for an automaton to acknowledge
that an input string is in the language?

Is it "a string S is in language L defined by automaton A if and only
if A halts in an accept state on input S"?

Or is it, perhaps "a string S is in language L defined by automaton A if
and only if A halts on input S"?

Either way, I'd say that the language L defined by an automaton A that
takes no input is either is either all strings or no strings.

If you layer on the requirement that the automaton actually read
the entire input then the language L consists of either the
set containing the empty string or the empty set depending on whether
the machine accepts or rejects the empty input.

None of this is substantive. It's all an artifact of details in
definitions. Much like the question of whether 0 is a natural
number, in the end it doesn't really change anything.

        John Briggs

Relevant Pages

  • Re: The state machine of no input
    ... >> I have been given a state machine, which takes no input, even though it ... >> only language accepted by a state machine taking no input must be the ... >> string and then only if the starting state is an accepting state. ... > How did your textbook define what it means for an automaton to acknowledge ...
    (sci.math)
  • Re: Operator overloading in C
    ... All development of C as an independent language has ... making any changes or improvements to the standard ... The lack of a counted string data structure, ... Pointers can't be used for arg1 or arg2. ...
    (comp.std.c)
  • Re: syntax...
    ... B&D on the part of the language designer. ... probably handle concatenation of string literals by itself, ... bitwise XOR, or if not that, then exponentiation.) ...
    (comp.lang.misc)
  • Why C Is Not My Favourite Programming Language
    ... C has no string type. ... compiler take care of the rest. ... Why does any normal language ... the programmer fail. ...
    (comp.lang.c)
  • Re: Controlling Javascript from server side
    ... but five different language implementations here. ... 'true' means that the request must be handled asynchronously. ... There is exactly *no* reason for such a thing here. ... | percent-endoded string). ...
    (comp.lang.javascript)