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.

I really wish I knew what you were talking about, seems cool.

>>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.

> 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

>Wuss - we had to take 20 almost every term.

full time is 12 :-/

What is E DFA?

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) = ∑*.

Quote:

---

Originally Posted by B0bDole

>Wuss - we had to take 20 almost every term.

full time is 12 :-/

---

Fulltime for us was 16

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 :)

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

er edit...kinda missed the other posts....

I figured out the other solution - and yours doesn't work SilentStrike

>>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.

yey for multiple posts!

>>What is E DFA?<<

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

Why doesn't it work?