AALL10 · Chapter 10Theory of Computation & Graphics🏛️ Past Licensure QuestionID: 0fd622ef

Which regular expression represents the set of all strings over $\Sigma = \{r, t\}$ that do NOT contain "rt" as a substring?

Multiple Choice Options

A
$(rt)^*$
B
$(tr)^*$
C
$(r^* t^*)$
D
$(t^* r^*)$
✓ Correct Option

Detailed Technical Solution & Explanation

A string contains the substring "rt" if any 'r' is followed by a 't'. To prevent "rt" from appearing anywhere, all 't's must appear before all 'r's (i.e., once an 'r' appears, no 't' can ever follow). This is precisely generated by the regular expression ** $t^* r^*$ ** (any number of 't's followed by any number of 'r's).

Option Analysis:

•

Option A (

(rt)^*

): Explicitly contains 'rt'.

•

Option B (

(tr)^*

): Generating strings like

trtr

contains "rt" internally.

•

Option C (

r^* t^*

): Generates

rt

when

r=1, t=1

•

Option D (

t^* r^*

): Correct; guarantees all 't's precede 'r's, completely preventing "rt".

Reference: Mock Test 05NEC Licensure Syllabus

Which regular expression represents the set of all strings over $\Sigma = \{r, t\}$ that do NOT contain "rt" as a substring?

Multiple Choice Options

Detailed Technical Solution & Explanation

Option Analysis:

Want to practice this topic interactively?

Which regular expression represents the set of all strings over $\Sigma = \{r, t\}$ that do NOT contain "rt" as a substring?

Multiple Choice Options

Detailed Technical Solution & Explanation

Option Analysis:

Want to practice this topic interactively?