Self-checkedTier 1 9 min readtoc.decidable-recognisable

Decidable and recognisable languages

Decidable (recursive) and Turing-recognisable (recursively enumerable) languages: definitions, the theorem that a language is decidable exactly when it and its complement are recognisable (run both recognisers in turn), closure properties of both classes, co-recognisable languages, the decidable problems about finite automata and grammars (acceptance, emptiness, equivalence for DFAs; acceptance and emptiness for CFGs) and the undecidable ones, with the Venn picture of all the classes.

Why it exists

A Turing machine may halt or loop. That gives two notions of "computable language": one for which a machine always answers (a decider) and a weaker one for which it answers "yes" when the answer is yes and may never answer when it is no (a recogniser). The gap between the two notions is where undecidability lives. GATE asks: classify a language, say which closure properties hold, which problems about automata and grammars are decidable.

Prerequisites

TM variants and the Church-Turing thesis

You need Turing machines, the notion of halting and looping, and the equivalence of the machine variants (TM variants).

Precise definitions

For a language $L \subseteq \Sigma^*$ :

$L$ is Turing-recognisable (recursively enumerable, r.e.) if some Turing machine $M$ accepts exactly the strings of $L$ : on $w \in L$ it halts and accepts; on $w \notin L$ it rejects or loops.
$L$ is decidable (recursive) if some Turing machine $M$ halts on every input and accepts exactly the strings of $L$ .
$L$ is co-recognisable (co-r.e.) if its complement $\overline{L} = \Sigma^* \setminus L$ is recognisable.

Every decidable language is recognisable. The classes, with the Chomsky hierarchy inside:

$\text{regular} \subsetneq \text{CFL} \subsetneq \text{context-sensitive} \subsetneq \text{decidable} \subsetneq \text{recognisable} \subsetneq \text{all languages}.$

(the middle strict inclusions are quoted; the last one is shown on the next page.) A problem is encoded as a language of strings: for example $A_{DFA} = \{\langle B, w \rangle : B \text{ is a DFA that accepts } w\}$ .

How it works

The basic theorem

$L$ is decidable $\iff$ $L$ and $\overline{L}$ are both recognisable.

( $\Rightarrow$ ) A decider for $L$ is a recogniser for $L$ ; swapping its accept and reject answers gives a decider, hence a recogniser, for $\overline{L}$ . ( $\Leftarrow$ ) Let $M_1$ recognise $L$ and $M_2$ recognise $\overline{L}$ . On input $w$ run $M_1$ and $M_2$ in turn, one move each (or on two tapes at once): $w$ is in exactly one of $L$ and $\overline{L}$ , so exactly one of the machines accepts, after finitely many moves. Accept if $M_1$ accepts; reject if $M_2$ accepts. This always halts. Example: $L$ = "contains $b$ ". $M_1$ accepts when it meets a $b$ (and runs for ever on $a^*$ ); $M_2$ accepts strings in $a^*$ when it meets the blank (and rejects on $b$ ). The table shows the rounds:

A decider from a recogniser for L and one for its complement: start

Computed by a script, not typed

string	verdict	rounds until one accepts	which recogniser accepted
ε
a
aaa
b
ab
aab
ba
aaaaab

Step 0

Run the two recognisers one move at a time in turn. Every string is accepted by exactly one of them, so one of them eventually accepts and the verdict is certain: this is how 'L and its complement both recognisable' gives 'L decidable'.

0 / 8

computed by script: the machine is simulated or the sets are constructed by scripts/toc_lib.py, one step at a time. python3 scripts/gen-toc5-traces.py

The verdict equals the predicate on all strings up to length $8$ and the number of rounds equals the number of moves of the machine that accepts.

Consequence. If a language is recognisable but not decidable, then its complement is not recognisable (otherwise the language would be decidable). Hence the class of recognisable languages is not closed under complement.

Enumerators

A language is recognisable iff some enumerator prints it (TM variants): the dovetailing table of the previous page shows how a recogniser that loops on some strings is turned into an enumerator. An infinite language is decidable iff some enumerator prints it in increasing order (shortlex order: shorter strings first, strings of equal length alphabetically). To decide $w$ , run the enumerator until it prints $w$ (accept) or prints a string that comes after $w$ in the order (reject, because $w$ would have appeared before). Every finite language is decidable anyway.

Closure properties

operation	decidable	recognisable
union	yes	yes
intersection	yes	yes
complement	yes	no
concatenation	yes	yes
star	yes	yes
reversal	yes	yes
difference	yes	no

(Quoted; the constructions are the obvious ones with the dovetailing trick for union of recognisers: run both machines in turn. Intersection: run both and accept if both accept. Complement of a decider: swap the answers. Complement of a recogniser fails, as shown by the basic theorem together with an undecidable recognisable language.)

Decidable problems about finite automata and grammars

All of these are languages of encodings; each is decidable by an algorithm:

problem	what is asked	decision procedure
$A_{DFA}$ , $A_{NFA}$ , $A_{REX}$	does the automaton (expression) accept $w$	simulate (with the subset construction for an NFA, conversion for an expression)
$E_{DFA}$	is the language empty	search the graph: is an accepting state reachable?
$EQ_{DFA}$	do two DFAs accept the same language	search the product for a pair that disagrees (minimisation)
$ALL_{DFA}$ , $FINITE_{DFA}$	all strings; finite language	complement and emptiness; graph search for a cycle on a path from the start to an accepting state
$A_{CFG}$	does the grammar generate $w$	CYK after converting to Chomsky normal form (normal forms)
$E_{CFG}$	is the language empty	mark the generating variables; the language is empty iff the start variable is not generating
$A_{LBA}$	does a linear bounded automaton accept $w$	simulate for as many moves as there are configurations (quoted)

The procedures for DFAs were checked on the regular-language pages; for grammars the emptiness test was compared with an independent computation of a shortest generated string (whose witness was verified by CYK) and CYK was compared with membership on 150 random grammars.

Undecidable problems (previews)

$A_{TM}$ (does $M$ accept $w$ ) is recognisable but not decidable; $HALT_{TM}$ likewise (halting problem).
$E_{TM}$ , $EQ_{TM}$ , $REGULAR_{TM}$ and every other non-trivial property of the language of a Turing machine (Rice's theorem).
$EQ_{CFG}$ (do two grammars generate the same language), $ALL_{CFG}$ (does a grammar generate every string), ambiguity of a grammar, and emptiness of the intersection of two context-free grammars (quoted).
$E_{LBA}$ is undecidable although $A_{LBA}$ is decidable (quoted).

Worked examples

EX 1Decidable or recognisable

Easy

A DFA's language: decidable. $\{a^n b^n c^n\}$ : decidable (the machine of the previous page always halts). "The set of strings $\langle M \rangle$ such that $M$ halts on the empty input": recognisable (simulate), not decidable. Its complement: not recognisable.

EX 2Use of the basic theorem

Easy

$L$ is recognisable and $\overline{L}$ is recognisable $\Rightarrow$ $L$ is decidable. If $L$ is recognisable but not decidable, $\overline{L}$ is not recognisable. A language and its complement can both fail to be recognisable; then neither of them is decidable.

EX 3Running two machines in turn

Medium

For "contains $b$ ": on $aaaaab$ , $M_1$ accepts at its sixth move, while $M_2$ halts and rejects when it reaches the $b$ (no transition); the combined machine accepts after $6$ rounds. On $aaa$ , $M_2$ accepts at the blank: after $4$ rounds the combined machine rejects. If only $M_1$ were available, on $aaa$ it would run for ever with no answer.

EX 4Union of two recognisable languages

Medium

$L_1 \cup L_2$ with recognisers $M_1$ , $M_2$ : run both in turn on $w$ and accept as soon as either accepts. If neither accepts, the combined machine runs for ever, which is allowed for a recogniser. Running $M_1$ to completion first would be wrong: if $M_1$ loops on $w$ but $M_2$ accepts $w$ , the combined machine would never answer.

EX 5Typical questions

GATE level

(a) "Recursive languages are closed under complement." True; recursively enumerable languages are not. (b) "A language $L$ and its complement are both r.e. $\Rightarrow$ $L$ is:" recursive. (c) "Is $E_{DFA}$ decidable? $EQ_{CFG}$ ?" Yes; no. (d) "The set of all decidable languages is countable." True: there are countably many machines. (e) "Every context-free language is decidable." True (CYK). (f) "If $L_1$ is recursive and $L_2$ is r.e., then $L_1 \cap L_2$ is:" recursively enumerable.

Cheat box

Recognisable (r.e.): a machine accepts exactly $L$ , may loop outside. Decidable (recursive): a machine always halts.
$L$ decidable $\iff$ $L$ and $\overline{L}$ recognisable (run both in turn).
Decidable closed under complement and all usual operations; recognisable not closed under complement.
Decidable: $A_{DFA}$ , $E_{DFA}$ , $EQ_{DFA}$ , $A_{CFG}$ , $E_{CFG}$ . Undecidable: $A_{TM}$ , $HALT$ , $E_{TM}$ , $EQ_{CFG}$ , $ALL_{CFG}$ .
Chain: regular $\subset$ CFL $\subset$ CSL $\subset$ decidable $\subset$ recognisable.

Traps and GATE patterns

Connections

Builds on

TM variants and the Church-Turing thesis

Unlocks

Decision problems for CFLsuses Turing machinesimplemented by TM variants and the Church-Turing thesisimplemented by Halting problem and reductionsPrerequisite of Halting problem and reductionsuses Rice's theoremuses

Across subjects

No cross-subject links yet.

Within this subject

TM variants and the Church-Turing thesisuses Halting problem and reductionsimplemented-by Closure properties of regular languagesanalogous-to Chomsky hierarchyuses

The proof that recognisable languages are not closed under complement uses a recognisable but undecidable language, found on the next page (undecidability); the same pattern of decidable versus undecidable problems appears for regular languages (closure properties) and in the hierarchy (Chomsky hierarchy).

PYQs

18 previous year questions from your book. I re-solved each one myself (1 by running or simulating, 17 by reasoning only); the book's key is shown next to my answer. All PYQs

GATE 2016 · Set 1 · MCQQ35 · page 201 of the book

Which of the following decision problems are
undecidable?
I. Given NFAs N1 and N2, is L(N1) ∩ L(N2) = φ?
II. Given a CFG G = (N, Σ, P, S) and a string x ε Σ*,
does x ε L(G)?
III. Given CFGs G1 and G2, is L(G1) = L(G2)?
IV. Given a TM, M is L(M) = φ ?

(a)I and IV only
(b)II and III only
(c)III and IV only
(d)II and IV only THEORY OF COMPUTATION

GATE 2023 · MSQQ11 · page 226 of the book

Which of the following statements is/are CORRECT?

(a)The intersection of two regular languages is regular.
(b)The intersection of two context-free languages is context-free.
(c)The intersection of two recursive languages is recursive.
(d). The intersection of two recursively enumerable languages is recursively enumerable.

GATE 2009 · MCQQ32 · page 229 of the book

Which one of the following is FALSE?

(a)There is a unique minimal DFA for every regular language
(b)Every NFA can be converted to an equivalent PDA.
(c)Complement of every context-free language is recursive.
(d)Every nondeterministic PDA can be converted to an equivalent deterministic PDA.

GATE 2006 · MCQ · 2 marksQ44 · page 231 of the book

For s ∈ (0+1)* let d(s) denote the decimal value of s (e.g.
d(101)=5 ). Let L={s∈(0+1)* |d(s) mod 5=2 and d(s)
mod 7≠4}
Which one of the following statements is true?

(a)is recursively enumerable, but not recursive
(b)is recursive, but not context-free
(c)is context-free, but not regular
(d)is regular

GATE 2026 · Set 2 · MSQ · 1 markQ1 · page 241 of the book

Which one of the following statements is equivalent to the
following assertion?
Turing machine M decides the language L ⊆ {0,1}*.

(a). Turing machine M halts on all input strings in {0,1}*
(b). Turing machine M accepts all input strings in L
(c). Turing machine M rejects all input strings in {0,1}* - L
(d).Turing machine M accepts all input strings in L and rejects all input strings in {0,1}*-L

GATE 2022 · MSQ · 1 markQ3 · page 241 of the book

Which of the following statements is/are TRUE?

(a)Every subset of a recursively enumerable language is recursive.
(b)If a language L and its complement I are both recursively enumerable, then L must be recursive.
(c)Complement of a context-free language must be recursive.
(d)If L1 and L2 are regular, then L1∩L2 must be deterministic context-free.

GATE 2021 · MCQQ4 · page 241 of the book

Let <M> denote an encoding of an automaton M. Suppose
that Σ = {0, 1}. Which of the following languages is/are
NOT recursive?

(a)L= {<M>| M is a DFA such that L(M) = ∅}
(b)L = {<M>| M is a DFA such that L(M) = Σ*}
(c)L= {<M>| M is a PDA such that L(M) = ∅}
(d)L = {<M>| M is a PDA such that L(M) = Σ*

GATE 2019 · MCQQ6 · page 241 of the book

Consider the following sets:
S1. Set of all recursively enumerable languages over the
alphabet {0,1}
S2. Set of all syntactically valid C programs
S3. Set of all languages over the alphabet {0,1}
S4. Set of all non-regular languages over the alphabet
{0,1}
Which of the above sets are uncountable?

(a)S2 and S3
(b)S3 and S4
(c)S1 and S4
(d)S1 and S2

GATE 2018 · MCQ · 1 markQ7 · page 241 of the book

The set of all recursively enumerable languages is:-

(a)closed under complementation.
(b)closed under intersection.
(c)a subset of the set of all recursive languages.
(d)an uncountable set. THEORY OF COMPUTATION

GATE 2017 · Set 1 · MCQ · 2 marksQ10 · page 242 of the book

Let A and B be finite alphabets and let # be a symbol
outside both A and B. Let f be a total function from A*
to B*. We say f is computable if there exists a Turing
machine M which given an input x  ∈  A*, always halts
with f(x) on its tape. Let Lf denote the language {x #
f(x)│x ∈ A* }. Which of the following statements is
true:

(a)f is computable if and only if Lf is recursive.
(b)f is computable if and only if Lf is recursively enumerable.
(c)If f is computable then Lf is recursive, but not conversely.
(d)If f is computable then Lf is recursively enumerable, but not conversely.

GATE 2016 · Set 2 · MCQ · 1 markQ11 · page 242 of the book

Consider the following types of languages:
L1: Regular
L2: Context-free
L3: Recursive
L4: Recursively enumerable.
Which of the following is/are TRUE?
I. L3' ∪ L4 is recursively enumerable .
II. L2' ∪ L3 is recursive .
III. L1* ∪ L2 is context-free .
IV. L1 ∪ L2' is context-free.

(a)I only
(b)I and III only
(c)I and IV only
(d)I, II and III only

GATE 2015 · Set 2 · MCQ · 1 markQ13 · page 242 of the book

Consider the following statements.
I. The complement of every Turing decidable language is
Turing decidable
II. There exists some language which is in NP but is not
turing decidable
III. If L is a language in NP, L is turing decidable
Which of the above statements is/are true?

(a)Only II
(b)Only III
(c)Only I and II
(d)Only I and III THEORY OF COMPUTATION

GATE 2015 · Set 1 · MCQQ14 · page 243 of the book

For any two languages L1 and L2 such that L1 is
context-free and L2 is recursively enumerable but not
recursive, which of the following is/are necessarily
true?
1. L1' (complement of L1) is recursive.

2. L2' (complement of L2) is recursive.
3. L1' is context-free.
4. L1' ∪ L2 is recursively enumerable.

(a)I only
(b)III only
(c)III and IV only
(d)I and IV only

GATE 2014 · Set 3 · MCQ · 1 markQ17 · page 243 of the book

Let Σ be a finite non-empty alphabet and let 2Σ* be the
power set of Σ*. Which one of the following is TRUE?

(a)Both 2Σ* and Σ* are countable
(b)2Σ* is countable and Σ* is uncountable
(c)2Σ* is uncountable and Σ* is countable
(d)Both 2Σ* and Σ* are uncountable

GATE 2013 · MCQ · 2 marksQ19 · page 243 of the book

Which of the following statements is/are FALSE?
1. For every non-deterministic Turing machine, there
exists an equivalent deterministic Turing machine.
2. Turing recognizable languages are closed under union
and complementation.
3. Turing decidable languages are closed under
intersection and complementation.
4. Turing recognizable languages are closed under union
and intersection.

(a)1 and 4 only
(b)1 and 3 only
(c)2 only
(d)3 only

GATE 2008 · MCQ · 2 marksQ21 · page 243 of the book

Which of the following statements is false?

(a)Every NFA can be converted to an equivalent DFA
(b)Every non-deterministic Turing machine can be converted to an equivalent deterministic Turing machine
(c)Every regular language is also a context-free language
(d)Every subset of a recursively enumerable set is recursive THEORY OF COMPUTATION

GATE 2006 · MCQ · 1 markQ26 · page 244 of the book

Let L1 be a regular language, L2 be a deterministic
context-free language and L3 a recursively enumerable,
but not recursive, language. Which one of the following
statements is false?

(a)L1 ∩ L2 is a deterministic CFL
(b)L3 ∩ L1 is recursive
(c)L1 U L2 is context free
(d)L1 ∩ L2 ∩ L3 is recursively enumerable

GATE 2005 · MCQQ27 · page 244 of the book

Let L1 be a recursive language, and let L2 be a
recursively enumerable but not a recursive language.
Which one of the following is TRUE?

(a)L1' is recursive and L2' is recursively enumerable
(b)L1' is recursive and L2' is not recursively enumerable
(c)L1' and L2' is recursively enumerable
(d)L1' is recursively enumerable and L2' is recursive

Self-check

Question 1

If $L$ is recognisable and not decidable, is $\overline{L}$ recognisable?

Show answer

No. If both were recognisable, $L$ would be decidable.

Question 2

How does a decider for $L$ follow from recognisers for $L$ and $\overline{L}$ ?

Show answer

Run both in turn on the input; exactly one accepts after finitely many moves; answer accordingly.

Question 3

Is the emptiness problem for context-free grammars decidable? How?

Show answer

Yes: compute the generating variables; the language is empty exactly when the start variable is not generating.

Question 4

Is the union of two recognisable languages recognisable? Why must the machines be run in turn?

Show answer

Yes. If the first machine loops on a string that the second accepts, running the first to the end would never reach the second.

Revision card

One-screen revision

Decidable $\subset$ recognisable; decidable $\iff$ $L$ and $\overline{L}$ both recognisable.
Decidable closed under complement; recognisable not.
Decidable: DFA/CFG acceptance and emptiness, DFA equivalence. Undecidable: $A_{TM}$ , $HALT$ , $E_{TM}$ , $EQ_{CFG}$ .
Run machines in turn, never one after another.

References

·Sipser, Introduction to the Theory of Computation (3rd edition), Section 3.2 (Turing-recognisable and decidable languages) and Section 4.1 (decidable languages about finite automata and grammars)
·Hopcroft, Motwani, Ullman, Introduction to Automata Theory, Languages, and Computation (3rd edition), Section 8.2.3 and Chapter 9 (recursive and recursively enumerable languages), Sections 4.3 and 7.4 (decision problems for regular and context-free languages)

Verification

scripts/enum-checks/toc_compute.py: a decider for 'contains b' built from a recogniser for the language and a recogniser for its complement (both run one move at a time) equals the predicate on all strings up to length 8, and the number of rounds equals the number of moves of the accepting machine; the dovetailing enumerator prints each member once; the DFA equivalence, emptiness and finiteness procedures were checked on the regular-language pages (product search, bounded search, graph search); for context-free grammars the emptiness test (a variable is generating) equals an independent shortest-string fixpoint whose witness string is verified by CYK on 150 random grammars, and CYK membership equals membership in the language. That A_TM is recognisable but not decidable follows from the universal program (checked on the previous page) and the diagonal argument on the next page. The closure tables, the undecidability of equivalence and universality of context-free grammars, and the statements about linear bounded automata are standard textbook results, QUOTED and not machine-proved (needs verification). Textbook chapter references are from memory. SECOND PASS (2026-11-02, done by the assistant, not a human check): every Self-check question was solved before the printed answer was read and all agreed; the definitions, worked examples, cheat box and traps were read claim by claim and the numbers re-derived by hand or by a small script (state counts, derivations, parse-tree and move counts, decomposition counts); tables and animations are machine output and were read, not re-run; No other defect found. Status raised to self-checked; verified needs a textbook or human check.

last verified: never

My notes (saved in this browser)

TM variants and the Church-Turing thesis

Halting problem and reductions