# another theory of computation problem

• 11-11-2004
axon
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.
• 11-12-2004
Darkness
I really wish I knew what you were talking about, seems cool.
• 11-12-2004
axon
>>I really wish I knew what you were talking about, seems cool.<<

THanks for letting me know! :rolleyes:

;) it is cool, but quite complicated - esspecially when you're taking 18 credit hours in total.
• 11-12-2004
Govtcheez
> 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. :p
• 11-12-2004
B0bDole
>Wuss - we had to take 20 almost every term.

full time is 12 :-/
• 11-12-2004
SilentStrike
What is E DFA?
• 11-12-2004
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) = ∑*.
• 11-12-2004
Govtcheez
Quote:

Originally Posted by B0bDole
>Wuss - we had to take 20 almost every term.

full time is 12 :-/

Fulltime for us was 16
• 11-12-2004
Darkness
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 :)
• 11-12-2004
SilentStrike
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
• 11-12-2004
axon
er edit...kinda missed the other posts....

I figured out the other solution - and yours doesn't work SilentStrike
• 11-12-2004
axon
>>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.
• 11-12-2004
axon
yey for multiple posts!

>>What is E DFA?<<

the 'E' stands for emptiness; used for emptiness testing
• 11-12-2004
SilentStrike
Why doesn't it work?