Register

TOC-Regular Expression

1,576 views
2 2 votes
Consider the following grammar which is not regular but it generates a regular language.
S → SSS|a|ab
Which of the following regular expression best describes the language ?

a. ((a + ab) (a + ab) (a + ab))*
b. ((a + ab)* (a + ab)* (a + ab)*)*
c. (a + ab) ((a + ab) (a + ab))*
d. None of these

2 Answers

Best answer
2 2 votes

Here by elimination technique we can work out.Let us see how..

We consider the minimal string which is a according to the grammar due to the production S --> a and hence epsilon is not produced.However  , both option A) and B) options' regular expressions accepts epsilon which is wrong accoding to the given grammar.Hence options A) and B) can be eliminated straightaway.

Now coming to option C) , we know minimal string generated by the grammar is 'a' now using the production S --> SSS we can have aaa as new string which satisifies the given regular expression.Similarly substituting one S as 'a' , one S as 'aaa' and final S as 'ab' , we get the new string as 'aaaaab' which is also satisfied by the given regular expression.

Similarly proceeding we can generate the strings from the grammar and then validate using the given regular expression.If even a single violation is found , we say the regular expression for the given grammar is incorrect.

But here no violation occurs.

Hence C) should be the correct option.

• selected by
2 2 votes

S → SSS|a|ab
RE = (a + ab) ((a + ab) (a + ab))*

:: Verification is very simple. Just check production it will generate some string of length >=1. 

  • Option A also generate null length string.
  • Option B also generate null string.

Answer will be option C.

• edited by
Voting & Accepting an answer helps improve the community
← Previous · TOC-PDANext → · DMA -cycle stealing
← Previous in category · TOC-PDANext in category → · TOC_Regular Expressi...
Position:
Show:

Related questions

3 3 votes
2 2 answers
294
294 views
GO Classes asked Oct 23, 2025
294 views
GO Classes DPP | TOC|REGULAR EXPRESSION
Consider the following three regular expressions over the alphabet $\Sigma=\{0,1\}$ :$p=\left(1^* 01^* 0\right)^* 1^*$ $q=\left(0^* 10^* 1\right)^* 0^*$ $r=((0+1)(0+1))^*...
3 3 votes
1 1 answer
321
321 views
GO Classes asked Oct 23, 2025
321 views
GO Classes DPP | TOC|REGULAR EXPRESSION
Let $\mathrm{p}, \mathrm{q}$, and r be three regular expressions over the alphabet $\Sigma=\{a, b\}$.$p=a(a+b)^* b$ $q=(a+b)^* a b(a+b)^*$ $r=a a^* b b^*$Which of the fol...
0 0 votes
2 2 answers
225
225 views
SUBRATA_DAS 2 asked Apr 10, 2025
225 views
TOC/REGULAR EXPRESSION.
in regular expression we use basically 4 operator. that is union, concatenation, kleene star, kleene plus.when we write regualr expression we use operator and operands.li...
1 1 vote
4 answers 4 answers
1.4k
1.4k views
Debargha Mitra Roy asked Jul 31, 2024
1,399 views
Regular Expression Model Practice Questions for GATE | TOC | Question-10
Find the equivalent of the Regular Expression: