PDA

View Full Version : another theory of computation problem



axon
11-11-2004, 09:40 PM
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.

Darkness
11-12-2004, 09:14 AM
I really wish I knew what you were talking about, seems cool.

axon
11-12-2004, 11:45 AM
>>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.

Govtcheez
11-12-2004, 01:11 PM
> 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

B0bDole
11-12-2004, 01:34 PM
>Wuss - we had to take 20 almost every term.

full time is 12 :-/

SilentStrike
11-12-2004, 01:35 PM
What is E DFA?

SilentStrike
11-12-2004, 01:42 PM
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) = ∑*.

Govtcheez
11-12-2004, 02:02 PM
>Wuss - we had to take 20 almost every term.

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

Darkness
11-12-2004, 02:42 PM
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 :)

SilentStrike
11-12-2004, 04:34 PM
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/www/slides/lect04.pdf

axon
11-12-2004, 07:09 PM
er edit...kinda missed the other posts....

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

axon
11-12-2004, 08:23 PM
>>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.

axon
11-12-2004, 08:24 PM
yey for multiple posts!

>>What is E DFA?<<

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

SilentStrike
11-12-2004, 08:54 PM
Why doesn't it work?