View Full Version : 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.

Darkness

11-12-2004, 09:14 AM

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.

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

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

SilentStrike

11-12-2004, 08:54 PM

Why doesn't it work?

Powered by vBulletin® Version 4.2.5 Copyright © 2019 vBulletin Solutions Inc. All rights reserved.