Past exam question: 2081 Chaitra (Regular), Q2(c)
Open in the Padhaiko appQuestion
Explain the decision properties of regular languages.
Solution
Decision Properties and Algorithms for Regular Languages: A property of a formal language class is decidable if there exists an effective algorithm (a halting Turing machine) that determines whether a given property holds for arbitrary input languages.
For regular languages (represented by DFAs ), the primary decision properties are:
- Emptiness Problem (?):
- Algorithm: Test whether any accepting state is reachable from start state using graph search (BFS or DFS) on the DFA transition graph.
- If no accept state is reachable, ; otherwise, . Time complexity: .
- Finiteness Problem (?):
- Algorithm: Remove unreachable and dead states. Detect whether any cycle exists in the remaining transition graph.
- If a cycle exists on a path from to an accept state, is infinite; if the graph is a directed acyclic graph (DAG), is finite.
- Membership Problem (?):
- Algorithm: Simulate DFA on input in linear time . Accept iff terminating state is in .
- Equivalence Problem (?):
- Algorithm: Form symmetric difference and test for emptiness. .
- Containment / Subset Problem (?):
- Algorithm: Construct DFA for and test if empty. .
Answer:
Regular languages have decidable decision algorithms for Emptiness (reachability of ), Finiteness (cycle detection on useful states), Membership ( DFA trace), Equivalence (emptiness of symmetric difference), and Containment ().