1
Q
How do you determine if a computational problem is decideable
A
If the corresponding language is decidable
We also say that the problem is solvable
2
Q
What does it mean for a language to be decidable
A
If there exists a TM that always halts and decides whether any given input string belongs to the language
3
Q
What is an undecidable language
A
Each turing machine that accepts L fails to halt on some w (string) in L
4
Q
A
Y2 Automata, Computation and Complexity
flashcards
Decks in class (9)
# Cards
-
Deterministic Finite Automata, Formal Definition of DFAs, Languages23
-
NFAs18
-
Composing Regular Languages, DFA Equivalence and RegEx18
-
Non-Regular Languages, Pumping Lemma and Applying Pumping Lemma8
-
Context-Free Languages/Grammars, Derivation Order and Derivation Trees35
-
Pushdown Automata24
-
Turing Machines26
-
Different Grammars5
-
Different Languages4
