Re: proving string has atmost k length whose NFA has k states


Rick Decker wrote:
Rupesh Bhochhibhoya wrote:
Hi everybody,

I'm new member of this group. My question is actually from the book by
Micheal Sisper chapter 1 ex:1.64. I can show that there is always a
string with atmost k-1 length for the NFA with k states but not able to
show string has atmost k states. Either I'm getting the question
incorrectly or my knowledge is insufficient or whatever. But I'm not
expecting for whole answer. I would be glad if i get some hints.


Thanks in advance..

Rupesh

It would have been helpful to state the question. I have a copy of
Sipser, but not everyone does (though perhaps they should--it's a
very good book, IMO). The problem states:

Let N be an NFA with k states that recognizes some language A.

(a) Show that, if A is nonempty, A contains some string of length
at most k.

The "at most k" part doesn't require that there _is_ a string
in A of length k; it just requires a that there is some string
in A of length <= k. As you correctly note, in this problem
"at most k" can be replaced with "less than k."

Actually, now that I think of it, I suspect that it should be
"less than k" for later use in part (b).


Regards,

Rick


Rick,

Thank you for the hint. Now I got how to proceed further. Thanks to
this group....


Sincerely, Rupesh

.

Relevant Pages

  • Re: Saving strings to ini file
    ... >> Writing code to read and write an ini for captions, hints and other text ... I'm not using THE ini file for language use, ... >> other string constants, things normally declared like ...
    (alt.comp.lang.borland-delphi)
  • Re: Is there a formula for conditional concatenating?
    ... i don't think MS people come in here to read "hints":) ... >> Sub concatvals() ... >> Dim strvalue As String ... >> Dim strsearch As String ...
    (microsoft.public.excel.worksheet.functions)
  • Re: proving string has atmost k length whose NFA has k states
    ... string with atmost k-1 length for the NFA with k states but not able to ... show string has atmost k states. ... The problem states: ... Let N be an NFA with k states that recognizes some language A. ...
    (comp.theory)
  • Re: Parsing, mid, left, trim or right to find specific word in string
    ... The OP specifically asked for hints only. ... Dim StringBeingSearched As String ... Notice that the msgbox only returns Aardvark not anteater. ...
    (microsoft.public.excel.programming)
  • Re: very simple encryption
    ... I just need a simple way to encrypt/decrypt a string, main purpose is, ... making it not readable by human eye, any hints on this? ...
    (comp.lang.java.programmer)