Module
Decidability and Recognizability
Sign in to add this module to your path and practice.
About
Deciders vs. recognizers. Recursive (decidable) vs. recursively enumerable (recognizable) languages. Decidable problems for regular and context-free languages (emptiness, finiteness, membership, equivalence where it holds). Universal TM.
Goal
Distinguish decide vs. recognize; prove standard automata/grammar problems decidable via constructive algorithms on DFAs/CFGs; describe a universal TM and its significance.
Unlocks
Tutor
Ask questions about this module.
Hi — I'm your tutor for Decidability and Recognizability. Ask about the concepts, goal, or where you're stuck.