GATE CS 2012 Q.25 (CS Q.25): Regular Expressions, Finite Automata and Regular Languages | GATE CS Mastery

Given the language $L = \{ab, aa, baa\}$ , which of the following strings are in $L^*$ ?

abaabaaabaa
aaaabaaaa
baaaaabaaaab
baaaaabaa

A

1, 2 and 3

B

2, 3 and 4

C

1, 2 and 4

D

1, 3 and 4

Official answer and solution

Official answer: C
From: Official GATE 2012 answer key

Solution

Test each candidate string to determine if it can be partitioned into words from the language $L = \{ab, aa, baa\}$ .

The language is $L = \{ab, aa, baa\}$ . Note the properties of the words in $L$ :

Every occurrence of character $b$ must be followed by at least one $a$ (specifically, either $ba$ in $baa$ or $b$ followed by $a$ from another block). Crucially, no word in $L$ ends in $b$ , so no string in $L^*$ can end with $b$ .

Test string 1: abaabaaabaa

Partition into blocks: (ab) (aa) (baa) (ab) (aa)
All constituent words $ab, aa, baa, ab, aa \in L$ .
Therefore, string 1 is in $L^*$ .

Test string 2: aaaabaaaa

Partition into blocks: (aa) (aa) (baa) (aa)
All constituent words $aa, aa, baa, aa \in L$ .
Therefore, string 2 is in $L^*$ .

Test string 3: baaaaabaaaab

The string ends with the letter b. Since every word in $L$ ends in b's following letter a (either $ab$ , $aa$ , or $baa$ ), any concatenation of words in $L$ must terminate with the letter a.
Hence, string 3 cannot be formed from $L$ , so $3 \notin L^*$ .

Test string 4: baaaaabaa

Partition into blocks: (baa) (aa) (ab) (aa)
All constituent words $baa, aa, ab, aa \in L$ .
Therefore, string 4 is in $L^*$ .

Thus, strings 1, 2, and 4 belong to $L^*$ .

Final answer

C

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2012 Computer Science and Information Technology (CS)
Question: 25 of 65, printed as CS Q.25
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.