Which is not the correct statement?
2012
Which is not the correct statement?
Answer: B. The class of regular sets is not closed under inverse homomorphisms. — Concept — a class of languages is closed under an operation when applying that operation to members of the class always yields a language that is again in the…
- A.
The class of regular sets is closed under homomorphisms.
- B.
The class of regular sets is not closed under inverse homomorphisms.
- C.
The class of regular sets is closed under quotient.
- D.
The class of regular sets is closed under substitution.
Attempted by 8 students.
Show answer & explanation
Correct answer: B
Concept — a class of languages is closed under an operation when applying that operation to members of the class always yields a language that is again in the class. For the class of regular sets, a closure claim is settled constructively: starting from a finite automaton or a regular expression for the given language, one builds a finite automaton or a regular expression for the result. If such a construction works for every input, closure holds; a closure claim is refuted only by producing a counterexample.
Application — the four operations named in the options are tested one at a time.
Homomorphism. A homomorphism h replaces every alphabet symbol a by a fixed string h(a). Substituting the string h(a) for each occurrence of a in a regular expression for L again produces a regular expression, so the homomorphic image of a regular set is regular. The statement that the class of regular sets is closed under homomorphisms is therefore true.
Inverse homomorphism. Here h−1(L) = { w : h(w) ∈ L }. Take a DFA A = (Q, Σ, δ, q0, F) for L and build B over the same state set Q with δ′(q, a) = δ*(q, h(a)), keeping q0 and F. Reading the single symbol a in B performs exactly the run that A makes on the whole string h(a), so B accepts w precisely when A accepts h(w). B is a finite automaton, hence h−1(L) is regular and the class of regular sets IS closed under inverse homomorphisms. The statement denying that closure is the false one.
Quotient. The quotient L1/L2 = { x : xy ∈ L1 for some y ∈ L2 }. Take a DFA for L1 and mark a state q as accepting exactly when some word of L2 drives the automaton from q into an accepting state; the transitions are unchanged. The result is again a DFA, so the class is closed under quotient — and this holds even when L2 is an arbitrary language. The statement is true.
Substitution. A substitution s replaces each alphabet symbol a by a whole language s(a). When every s(a) is regular, replacing a by a regular expression for s(a) inside a regular expression for L again gives a regular expression, so the substituted language is regular. The statement is true.
Cross-check — inverse homomorphism is one of the best-behaved operations in formal language theory: both the regular and the context-free languages are closed under it, which is why it is standard equipment in non-closure and non-regularity arguments. Three of the four statements assert closure under homomorphism, under quotient and under substitution, and all three are standard closure theorems for regular sets. The only statement that contradicts a standard theorem is the claim that the class of regular sets is not closed under inverse homomorphisms, so that is the statement which is not correct.
Explore the full course: Mppsc Assistant Professor Computer Science Paper 2