The new forums will be named Coin Return (based on the most recent vote)! You can check on the status and timeline of the transition to the new forums here.
Please vote in the Forum Structure Poll. Polling will close at 2PM EST on January 21, 2025.
Understanding Computational Theory
Althane
Registered User regular
Registered User regular
I'm studying for my Computational Theory class (test today), and the first problem in the review sheet is really stumping me. I've managed to figure out solutions to everything else (half of them are "Create an algorithm for a Turing Machine", the other half are "Is it decidable?", the one I'm having trouble with is of the latter form), but this one has got me totally lost.
"1.Explain why it is decidable to determine whether a given DFA accepts a word that has more 1's than 0's."
These are my notes (we had a review session yesterday, and by review session I mean "He tells us the answers and doesn't explain anything" (really lousy professor)):
"Perform the cartesian product. The intersection of a CFL, and a regular language, is a CFL. The language of having more 1's than 0's can be described by a PDA, and you can run the PDA and the DFA together. (3 machines! I... don't understand)"
I could think of why it ISN'T decidable (the set of words having more 1's than 0's is infinite), but apparently it IS decidable... so could someone help explain it to me?
*feels stupid*
"1.Explain why it is decidable to determine whether a given DFA accepts a word that has more 1's than 0's."
These are my notes (we had a review session yesterday, and by review session I mean "He tells us the answers and doesn't explain anything" (really lousy professor)):
"Perform the cartesian product. The intersection of a CFL, and a regular language, is a CFL. The language of having more 1's than 0's can be described by a PDA, and you can run the PDA and the DFA together. (3 machines! I... don't understand)"
I could think of why it ISN'T decidable (the set of words having more 1's than 0's is infinite), but apparently it IS decidable... so could someone help explain it to me?
*feels stupid*
Althane on
0