Properties of Regular Languages Questions and Answers

Answer: C

The statement always true is \(L_{2}\) is context-free.

\(L_{2}\) is given to be regular, and every regular language is context-free.

Nothing useful is known about \(L_{1}\). Take \(L_{2} = \emptyset\), which is regular; then \(L_{1} \cap L_{2} = \emptyset\) is regular whatever \(L_{1}\) is. With \(L_{1} = \{a^{n}b^{n}\}\), \(L_{1}\) is not regular and \(L_{1} \cup L_{2} = L_{1}\) is not regular either. With \(L_{1} = \{a^{n}b^{n}c^{n}\}\), \(L_{1}\) is not even context-free. So the three statements about \(L_{1}\) can all fail.

Answer: A

The image is h(L) = {abab, abbbcab}.

A homomorphism replaces each symbol by its image string, and the image of a language is the set of images of its strings:

\[ \begin{aligned} h(aa) &= h(a)\,h(a) = ab\,ab = abab \\ h(aba) &= ab\,bbc\,ab = abbbcab \end{aligned} \]

L has only two strings, so h(L) has at most two. The strings aaaa and bbbb in options B and C are not images of anything in L, and option D's strings do not match h(a) = ab and h(b) = bbc.

Answer: A

The quotient is a*ba*.

The right quotient \(L_1/L_2\) is the set of strings x such that xy is in \(L_1\) for some y in \(L_2\). Here \(L_2 = ab^{*}\), so y is a followed by some b's. Every string of \(L_1 = a^{*}baa^{*}\) has a single b followed only by a's, so the only usable y is the one with no b's, y = a.

So x must satisfy \(xa \in a^{*}baa^{*}\), which means x is \(a^{*}ba^{*}\): any number of a's, the b, then any number of a's (possibly none, since the removed a supplies the one a* needs).

Option B forces exactly one a before the b, option C allows several b's, and option D uses a symbol c that does not occur.

Answer: A

The right quotient is \(L_{1}/L_{2} = \{x : xy \in L_{1}\) for some \(y \in L_{2}\}\).

The right quotient takes the strings of \(L_{1}\) that end in a string of \(L_{2}\) and removes that ending: x is in the quotient if appending some y from \(L_{2}\) gives a string of \(L_{1}\). For example, if \(L_{1} = \{ab, abb\}\) and \(L_{2} = \{b\}\), then \(L_{1}/L_{2} = \{a, ab\}\).

The second definition simply returns \(L_{1}\) itself, the third puts the concatenation in the wrong language, and the fourth uses the notation for set difference.

Answer: B

The pumping lemma is used for proving a language is not regular.

The lemma states a property that every regular language must have: any long enough string can be split as xyz so that xyⁱz stays in the language for every i ≥ 0. Showing that some string cannot be pumped this way proves, by contradiction, that the language is not regular.

It cannot prove a language regular, since some non-regular languages also satisfy the pumping condition. For that you build a DFA or a regular expression. It is not used to generate strings or simplify grammars.

Answer: B

The pumping lemma is used to prove that a given grammar is not regular, strictly, that the language it generates is not regular.

The lemma states a property every regular language has: long enough strings can be split as xyz with y pumpable. It is used by contradiction: show that some string of the language cannot be pumped, and the language cannot be regular.

Because it is only a necessary condition, it can never prove a language is regular. Equivalence of two regular expressions is decided by building and minimising their automata, not by the pumping lemma.

Answer: B

The statement that the class of regular sets is not closed under inverse homomorphisms is not correct, since regular sets are closed under inverse homomorphism: the inverse image of a regular language under a homomorphism is regular, which one shows by building an automaton that applies the homomorphism to the input. They are also closed under homomorphisms, quotient and substitution. So the statement that is not correct is the second one. The keyed answer is the second option.

Answer: C

S1 is correct and S2 is not, so the third option is right. Regular languages are closed under reversal and under concatenation, so if L is regular then L^R is regular and the concatenation of L with L^R is regular.

S2 claims that {w w^R} is regular, which is false. Recognising the second half as the mirror image of the first needs unbounded memory, which a finite automaton does not have, and the pumping lemma proves the language is not regular. So the options that call S2 correct are wrong, and S1 is not false either.

Answer: C

The right quotient L1/L2 is the set of strings x such that x y is in L1 for some y in L2. L1 is a*baa*, strings a^n b a^m with n at least 0 and m at least 1, and L2 is ab*, strings a, ab, abb and so on. A string y = ab^k with k at least 1 ends in b, but every string of L1 ends in a, so those y never match. Only y = a works: removing the last a from a^n b a^m leaves a^n b a^(m-1) with m - 1 at least 0, which is the language a*ba*. So the answer is (C). Option (A) a*b misses strings that keep trailing a's, and (B) a*baa* is L1 itself, so the quotient is not that and (D) is wrong as well.