PadhaikoAll subjects

Past exam question: 2081 Chaitra (Regular), Q2(c)

Theory of Computation · 3 marks

Open in the Padhaiko app

Topic: Closure Properties, Pumping Lemma & Decision Algorithms

Question

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:

  1. 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: .
  2. 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.
  3. Membership Problem (?):
    • Algorithm: Simulate DFA on input in linear time . Accept iff terminating state is in .
  4. Equivalence Problem (?):
    • Algorithm: Form symmetric difference and test for emptiness. .
  5. 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 ().

All past exam questions for Theory of Computation