Thread: another theory of computation problem

  1. #1
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572

    another theory of computation problem

    well I'm kind-of stuck on this question:

    Let ALL DFA = { <A> | A is a DFA that recognizes ∑* }. Show that ALL DFA is decidable.

    I have to prove this two different ways. So far I figured out one, and can't think of any other way...any ideas?

    here is the first solution:
    ______
    ALL DFA == E DFA, we know that E DFA is decidable (theorem 4.4) and since decidable languages are closed under the comlpement operation, ALL DFA is decidable.

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  2. #2
    Registered User
    Join Date
    Mar 2003
    Posts
    580
    I really wish I knew what you were talking about, seems cool.
    See you in 13

  3. #3
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    >>I really wish I knew what you were talking about, seems cool.<<

    THanks for letting me know!

    it is cool, but quite complicated - esspecially when you're taking 18 credit hours in total.

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  4. #4
    Mayor of Awesometown Govtcheez's Avatar
    Join Date
    Aug 2001
    Location
    MI
    Posts
    8,823
    > it is cool, but quite complicated - esspecially when you're taking 18 credit hours in total.

    Wuss - we had to take 20 almost every term.

  5. #5
    Bob Dole for '08 B0bDole's Avatar
    Join Date
    Sep 2004
    Posts
    618
    >Wuss - we had to take 20 almost every term.

    full time is 12 :-/
    Hmm

  6. #6
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    What is E DFA?
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

  7. #7
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    Actually.. this is quite easy. Let A be a DFA (thought it was a PDA first.. that had me perplexed), we want to determine if L(A) = ∑*. L(A) = ∑* iff there is no string that results in a rejection state when ran on your DFA. But a DFA is just a finte directed graph. So you just do a graph search from the start node of A. If you hit a rejecting final state, L(A) != ∑*, otherwise, L(A) = ∑*.
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

  8. #8
    Mayor of Awesometown Govtcheez's Avatar
    Join Date
    Aug 2001
    Location
    MI
    Posts
    8,823
    Quote Originally Posted by B0bDole
    >Wuss - we had to take 20 almost every term.

    full time is 12 :-/
    Fulltime for us was 16

  9. #9
    Registered User
    Join Date
    Mar 2003
    Posts
    580
    Quote Originally Posted by SilentStrike
    Actually.. this is quite easy. Let A be a DFA (thought it was a PDA first.. that had me perplexed), we want to determine if L(A) = ∑*. L(A) = ∑* iff there is no string that results in a rejection state when ran on your DFA. But a DFA is just a finte directed graph. So you just do a graph search from the start node of A. If you hit a rejecting final state, L(A) != ∑*, otherwise, L(A) = ∑*.
    Arg, well now that you put it THAT way it's obviously quite clearly an easy problem. Just take the result of that, divide it by the square root of the sine of PI times i raised to the negative infinity, plus 2...im so stoopid!

    I still really wish I knew what was going on...ill leave now
    See you in 13

  10. #10
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    It's really not a hard concept if you understand the terminology and the symbols.

    This is a reasonably clear explanation of what DFAs are. You can get the picture and the example at the bottom, and then work back to the nasty definitions and such.

    http://www.cse.nd.edu/courses/cse411...des/lect04.pdf
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

  11. #11
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    er edit...kinda missed the other posts....

    I figured out the other solution - and yours doesn't work SilentStrike
    Last edited by axon; 11-12-2004 at 08:21 PM.

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  12. #12
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    >>Wuss - we had to take 20 almost every term<<
    >>Fulltime for us was 16<<

    maybe it was a different load then, or hours per class. My 18 hours = 6 three hour classes, which is a lot! actually its the most you can take without a petition.

    How much was your calculus worth? chem? phys? in hours, that is.

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  13. #13
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    yey for multiple posts!

    >>What is E DFA?<<

    the 'E' stands for emptiness; used for emptiness testing

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  14. #14
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    Why doesn't it work?
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Memory problem with Borland C 3.1
    By AZ1699 in forum C Programming
    Replies: 16
    Last Post: 11-16-2007, 11:22 AM
  2. Someone having same problem with Code Block?
    By ofayto in forum C++ Programming
    Replies: 1
    Last Post: 07-12-2007, 08:38 AM
  3. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  4. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 06:54 PM
  5. Laptop Problem
    By Boomba in forum Tech Board
    Replies: 1
    Last Post: 03-07-2006, 06:24 PM