GATE Overflow | Mock GATE | Test 1 | Question: 65

Question

Consider the following operators used in an arbitrary regular expression parsing.
(In all the below statements, capital letters denote the operator. Ignore quotes.)
'xPy' denotes a double occurrence of either x or y.
'xQ' denotes zero or one occurrence of x
'ySxSz' denotes x should be preceded and followed by at least one occurrence of y and z respectively.
Given a regular expression: bSaSabPaaQ
Which of the following strings does not belong to the above given regular expression?

• A. bbaaabba
• B. baaabb
• C. bbbaaaa
• D. baabbaaaa

Comments

A can be generated in this way,but how B can be generated?

Answer 1

part 1.bSaSa means that a should be preceeded by atleast one occurence of b and followed by atleast one occurrence of a.

part 2.bPa means a double occurrence of either a or b

part 3.aQ means zero or one occurrence of a.

So in all the strings these rules need to be followed.We will break the strings into 3 part so that application of all the rules can be examined efficiently.

1. bbaaabba - 

         bb-a-aa part 1 

        bb means part 2 double occurence of b and a is part 3 one occurence of a So it belongs to the given regular expression.

       2.    baaabb 

         b-a-aa part 1 satisfied bb part 2 satisfied zero occurrence of a part 3 satisfied . So it also belongs to the regular expression.

       3. bbbaaaa 

       bbb-a-a part 1 satisfied aa part 2 satisfied  zero occurrence of a part 3 satisfied . So it also belongs to the regular expression

       4. baabbaaaa

      b-a-a part1 bb-part 2 but aaaa doesnt account here . So it does not belong to the regular expression.

 

Comments

it is given in the question that which of the strings does not belong to RE according to your explaination  D does not belong to RE so answer is 1

---

@suyash sayankar ya option 4 i.e d and only 1 doesnt belong to it

---

But in question it is not clearly told what they want
They want option number of string not in the regex or how many strings are not in regex.

It should have been designed as MCQ.

Answer 2

Convert $bSaSabPaaQ$  into standard regular expressions = $b^+aa^+(bb+aa)(\lambda + a)$. Now, it is very easy and efficient.

Answer 3

We can convert the rules as:

Rule1 = xPy = $(xx+yy+xxy+xyy)$

Rule2 = xQ = $(\epsilon + x)$

Rule3 = ySxSz = (yy*xzz*)

 

Convert the given regular expression:

bSaSaBPaaQ = $(bSaSa)(bPa)(a+\epsilon)$

=>$((Rule3)(Rule1)(Rule2))$

 

Now using bottom up parsing, it is easy to that above regex can't generate D.
$baabbaaaa$ => $(baa)bbaaaa$ => $(Rule1)bbaaaa$

Now we can either reduce $bba$ or $bb$ which will match to rule2 but in both reductions, there will be either $aaa$ or $aaaa$ remaining to be reduced which doesn't match Rule3.

(Please comment if I missed something or did something wrong.)