retagged by
1,150 views
2 votes
2 votes

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?

  1. bbaaabba
  2. baaabb
  3. bbbaaaa
  4. baabbaaaa
retagged by

3 Answers

4 votes
4 votes

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.

 

1 votes
1 votes
Convert $bSaSabPaaQ$  into standard regular expressions = $b^+aa^+(bb+aa)(\lambda + a)$. Now, it is very easy and efficient.
1 votes
1 votes
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.)
Answer:

Related questions