Exams › GATE › Technical

If L is a regular language over Σ = {a, b}, which one of the following languages is NOT regular?

1. L · L^R = {xy | x ∈ L, y^R ∈ L}
2. {ww^R | w ∈ L}
3. Prefix(L) = {x ∈ Σ* | ∃y ∈ Σ* such that xy ∈ L}
4. Suffix(L) = {y ∈ Σ* | ∃x ∈ Σ* such that xy ∈ L}

Correct answer: {ww^R | w ∈ L}

Solution

The language {ww^R | w ∈ L} is not regular because it requires matching a string with its reverse, which cannot be done by a finite automaton, as it lacks the memory to store an arbitrary length of 'w' for comparison.

Related GATE Technical questions

• A certain processor uses a fully associative cache of size 16 kB. The cache block size is 16 bytes. Assume that the main memory is byte addressable and uses a 32-bit address. How many bits are required for the Tag and the Index fields respectively in the addresses generated by the processor?
• Which one of the following kinds of derivation is used by LR parsers?
• In 16-bit 2’s complement representation, the decimal number −28 is:
• Let U = {1,2,...,n}. Let A = {(x,X)|x ∈ X, X ⊆ U}. Consider the following two statements on |A|. I. |A| = n2^(n−1) II. |A| = ∑(k=1 to n) k C(n,k) Which of the above statements is/are TRUE?
• Which one of the following is NOT a valid identity?
• Let X be a square matrix. Consider the following two statements on X. I. X is invertible. II. Determinant of X is non-zero. Which one of the following is TRUE?

⚔️ Practice GATE Technical free + battle 1v1 →