Formal Language Operations & Sets MCQs: 11 Solved Questions

Language-operation questions look short, but one changed symbol can change the whole set. It is easy to confuse ∅ with {ε}, count raw concatenation pairs without removing duplicates, or accept a Kleene-star split without joining it back. The 11 questions below keep their original exam wording: seven are multiple choice, two are numerical answer type, and two are longer subjective sets. Answer each one before reading its solution. Five carry their own practice page, linked from the question heading. For the other six, work from the Language Ops & Sets PYQ Questions hub.

Four language-operation rules to hold before solving

For L₁={10,1} and L₂={011,11}, the raw pairings are 10·011=10011, 10·11=1011, 1·011=1011, and 1·11=111. Thus L₁L₂={10011,1011,111} has 3 elements, not 4.

For membership in L={ab,aa,baa}, every character must be consumed. The split abaabaaabaa=ab·aa·baa·ab·aa succeeds. No complete split of baaaaabaaaab exists.

Kleene-star membership MCQs 1 to 3

Question 1 (MCQ)

Given the language L = {ab, aa, baa}, which of the following strings are in L*?
(1) abaabaaabaa
(2) aaaabaaaa
(3) baaaaabaaaab
(4) baaaaabaa

A. 1, 2 and 3
B. 2, 3 and 4
C. 1, 2 and 4
D. 1, 3 and 4

Answer: C. 1, 2 and 4. The successful splits are ab·aa·baa·ab·aa, aa·aa·baa·aa, and baa·aa·ab·aa. For string 3, a complete word-break search over the three allowed tokens reaches no valid end position. Starting with baa alone does not establish that rejection.

Question 2 (MCQ)

Let L = {ab, aa, baa}. Which of the following strings are not in L*.

A. abaabaaabaa
B. aaaabaaaa
C. baaaaabaaaab
D. baaaaabaa

Answer: C. baaaaabaaaab. Options A, B and D have the successful splits shown in Question 1. Every possible parse of C with ab, aa and baa stops before all 12 characters are consumed. Question 2 asks for that one non-member.

Question 3 (MCQ)

Consider L = {ab, aa, baa}.

Which of the following string is NOT in L*?

A. baaaaabaaaaa
B. abaabaaabaa
C. aaaabaaaa
D. baaaabaa

Answer: A. baaaaabaaaaa. B is ab·aa·baa·ab·aa, C is aa·aa·baa·aa, and D is baa·aa·baa. In A, the initial b forces baa, but no continuation from the allowed tokens consumes the remaining nine characters.

Complement and concatenation MCQs 4 and 5

Question 4 (MCQ)

Let Σ = {a, b} and language L = {aa, bb}. Then, the complement of L is

A. {λ, a, b, ab, ba} ∪ {w ∈ {a, b}* : |w| > 3}
B. {a, b, ab, ba} ∪ {w ∈ {a, b}* : |w| ≥ 3}
C. {w ∈ {a, b}* : |w| > 3} ∪ {a, b, ab, ba}
D. {λ, a, b, ab, ba} ∪ {w ∈ {a, b}* : |w| ≥ 3}

Answer: D. Remove only aa and bb from Σ*. The complement contains λ, both length-1 strings, ab, ba, and every string of length at least 3. A and C omit length-3 strings, while B omits λ.

Question 5 (MCQ)

Suppose L₁ = {10, 1} and L₂ = {011, 11}. How many elements are there in L = L₁L₂?

A. 4
B. 3
C. 2
D. None of these

Answer: B. 3. The four raw results are 10011, 1011, 1011 and 111. After the repeated 1011 collapses, the result is {10011,1011,111}. Therefore |L₁L₂| can be smaller than |L₁||L₂|.

Palindrome counts and language powers, Questions 6 to 8

Question 6 (NAT)

Let Σ = {a, b, c}.
Let x = the number of even-length palindromes over Σ with ∣w∣ ≤ 10.

Let y = the number of odd-length palindromes over Σ with ∣w∣ ≤ 21.

Find the value of x+y _______ .

There are no options. The answer is 266083. For even length 2k, the first k symbols determine the palindrome. Including length 0, x=Σₖ₌₀⁵3ᵏ=1+3+9+27+81+243=364. For odd lengths 1 through 21, y=Σⱼ₌₁¹¹3ʲ=(3¹²-3)/2=265719. Hence x+y=364+265719=266083.

Question 7 (MCQ)

Let L be a set of letters such that
L = {ϵ, a, b, …….., y, z}.
The set representing all 4 letter words is

A. L³ + L
B. L⁴ - L
C. L⁴ - L⁻¹
D. L⁴ - L³

Answer: D. L⁴ - L³. Since ϵ∈L, four choices can produce lengths 0 through 4, while L³ contains lengths 0 through 3. Their set difference keeps exactly the four-letter words. L⁻¹ is not a language power to use here.

Question 8 (NAT)

If L₁= {𝜀, 0, 1, 01, 11} then what is the cardinality of (L₁)² ?

There are no options. The answer is 17. Enumerating distinct results gives (L₁)²={𝜀,0,1,01,11,00,001,011,10,101,111,010,0101,0111,110,1101,1111}. That is 17 strings. The 25 raw pairs shrink because 𝜀·x=x·𝜀=x and other pairs also collide. Writing every distinct output is safer than multiplying cardinalities.

Empty-language algebra and mixed checks, Questions 9 to 11

Question 9 (MCQ)

Consider the languages:
L1=∅
L2={a}.
Which of the following represents:
L1 L2∗ ∪ L1∗ ?

A. {∅}
B. {ε∅}
C. {π}
D. {ε}

Answer: D. {ε}. Although L2*={ε,a,aa,...}, concatenating it with ∅ gives ∅. Separately, ∅*={ε} because the zero-concatenation case contributes the empty string. Therefore ∅∪{ε}={ε}. The language {∅} is a different object.

Question 10 (subjective)

Answer the following questions related to Formal Languages:
(a) Let L = {ab,aa,baa}. Explain the concept of Kleene Closure L∗. Determine whether the string “baaaaabaaaaa” belongs to L∗ with proper justification.
(b) Given L = {ab,aa,baa}, identify the strings that can be generated using concatenation of elements of L. Explain the method used.
(c) Let L₁ = ∅ and L₂ = {a}. Evaluate:
                         L₁L₂∗ ∪ L₁∗
(d) Let Σ = {a,b} and L = {aa,bb}. Find the complement of L with respect to Σ∗.

Model answer: (a) L* contains every concatenation of zero or more words from L, including ε. The 12-character string baaaaabaaaaa is not in L* because no token path consumes it fully. (b) Examples include ε, abaa=ab·aa, baaab=baa·ab, and aaaa=aa·aa; continue with any finite token sequence. (c) ∅L₂*=∅ and ∅*={ε}, so the result is {ε}. (d) The complement is Σ*\{aa,bb}, every string over {a, b} except aa and bb.

Question 11 (subjective)

Answer the following questions related to Formal Languages and Operations on Languages:
(a) Let L1 = {ϵ,0,1,01,11}. Compute the cardinality of (L1)² and justify your answer.
(b) Suppose L₁ = {10,1} and L2={011,11}. Find the number of distinct strings in L=L₁L₂.
(c) Let L={ab,aa,baa}. Determine whether the string “baaaaabaaaab” belongs to L∗. Justify your answer.

Model answer: (a) The 17-string enumeration in Question 8 gives |(L1)²|=17. (b) 10·011=10011, 10·11=1011, 1·011=1011, and 1·11=111, so there are 3 distinct strings. (c) baaaaabaaaab∉L*; no word-break path consumes all 12 characters. The tempting baa·aa·ab·aa·ab is not proof: it produces baaaaabaaab, an 11-character string, not the 12-character target string.

The traps these 11 questions expose

Use a six-check audit: join every proposed split back to the original string; count characters before using parity; list distinct strings instead of raw pairs; keep ∅, {∅} and {ε} separate; state the universe before a complement; include length 0 only when ε is permitted.

Continue with Regex and FA Equivalence MCQs for another focused set, Finite Automata MCQs for DFA and NFA practice, and Regular Expressions and the Pumping Lemma for the bridge from language descriptions to proofs.

Formal language operations: the short version and next step

Retest yourself on Questions 2, 5, 8, 9 and 11 without looking. Together they cover complete word breaking, duplicate elimination, exact power cardinality, empty-language algebra and verification of a proposed split. Write each intermediate set or sum on paper so a hidden collision or missing empty string cannot slip through. The short version is: L* includes ε; membership needs a complete tokenisation; concatenation returns distinct outputs; complements depend on Σ*; and free half positions determine a palindrome. For sequenced Theory of Computation study, use GATE Guidance by Sanchit Sir. When you are ready to work under time pressure, move to the GATE Test Series.