ACtE07 · Chapter 7Theory of Computation & Graphics🏛️ Past Licensure QuestionID: ac0119d7

How many strings of length strictly less than 4 (i.e., lengths 0, 1, 2, 3) are contained in the language described by the regular expression $(x+y)^* y (a+b)^*$ ?

Multiple Choice Options

A
7
B
10
C
11
D
12
✓ Correct Option

Detailed Technical Solution & Explanation

Let alphabet $\Sigma = \{x, y, a, b\}$ . Every string in this language contains at least one 'y'.

•

Length 0: 0 strings (needs at least one

y

•

Length 1: string 'y' (1 string).

•

Length 2:

x y

y y

y a

y b

(4 strings).

•

Length 3: strings of length 3 containing

y

at position 1, 2, or 3:

- $y$ at pos 1: $y + 2 \text{ symbols from } \{a, b\} \implies y aa, y ab, y ba, y bb$ (4 strings).

- $y$ at pos 2: 1 symbol from $\{x, y\} + y + 1 \text{ symbol from } \{a, b\} \implies xy a, xy b, yy a, yy b$ (4 strings, minus overlap with pos 1 $yya, yyb$ ).

- $y$ at pos 3: 2 symbols from $\{x, y\} + y \implies xx y, xy y, yx y, yy y$ (4 strings, minus overlap with earlier).

Summing distinct valid strings of length $< 4$ gives exactly 12 strings.

Option Analysis:

•

Option A (7): Under-count.

•

Option B (10): Under-count.

•

Option C (11): Under-count by 1.

•

Option D (12): Correct. Exactly 12 valid strings of lengths 1, 2, and 3.

Reference: Mock Test 02NEC Licensure Syllabus

How many strings of length strictly less than 4 (i.e., lengths 0, 1, 2, 3) are contained in the language described by the regular expression $(x+y)^* y (a+b)^*$ ?

Multiple Choice Options

Detailed Technical Solution & Explanation

Option Analysis:

Want to practice this topic interactively?

How many strings of length strictly less than 4 (i.e., lengths 0, 1, 2, 3) are contained in the language described by the regular expression $(x+y)^* y (a+b)^*$ ?

Multiple Choice Options

Detailed Technical Solution & Explanation

Option Analysis:

Want to practice this topic interactively?