decidable problems about automata
It helps to gather, in one place, the long list of questions about finite automata, regular expressions, and context-free grammars that have guaranteed-to-halt algorithms. Think of it as the toolbox of facts you can ALWAYS compute about these simpler models. The recurring reason they are all decidable is the same: a DFA has finitely many states and a fixed input produces a bounded run, and a CFG can be put into a normal form that bounds derivation length — so 'infinite-looking' questions collapse into finite searches.
For deterministic and nondeterministic finite automata and regular expressions, all of the following are decidable: does the machine accept a given string (acceptance); is its language empty (emptiness); is its language finite or infinite (a cycle-on-a-useful-path check); do two of them recognize the same language (equivalence, via the symmetric-difference-then-emptiness trick); is one language a subset of another (a related emptiness check); is the language all of Σ* (Sigma-star), i.e. universality (test the complement for emptiness). Because regular expressions, DFAs, and NFAs are all interconvertible by always-halting procedures (Thompson's construction, the subset construction, state elimination), a result for one transfers to the others. For context-free grammars, both membership (is w generated, via CYK) and emptiness (does it generate anything, via generating-symbol marking) are decidable, and finiteness is decidable too.
Knowing this catalogue is practically valuable and conceptually important. Practically, it tells a tool-builder which checks can be automated with confidence — regex equivalence, dead-code (useless-symbol) detection, reachability analysis. Conceptually, it draws the boundary that the next chapter crosses: the same questions become UNDECIDABLE once you move up to context-free grammars (equivalence, ambiguity, universality) or to Turing machines (acceptance, emptiness, equivalence, essentially everything nontrivial). The pattern is clean — more memory buys more expressive power but costs you algorithmic decidability.
Want to know if your regex matches every possible input (universality)? Convert it to a DFA, complement it, and run the emptiness test: the regex is universal iff the complement's language is empty. Want to know if two DFAs are equivalent? Symmetric-difference plus emptiness. Both always halt.
Most natural questions about DFAs/NFAs/regexes/CFGs reduce to acceptance, emptiness, or equivalence — all decidable.
Decidability is not uniform up the hierarchy. CFG equivalence, ambiguity, and universality are UNDECIDABLE even though CFG membership and emptiness are decidable; for Turing machines almost everything nontrivial is undecidable.