936 views
2 votes
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 votes
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 votes
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

Related questions

1 votes
1 votes
2 answers
1
1 votes
1 votes
2 answers
2
Ashish Roy 1 asked Sep 27, 2018
2,070 views
Given two Regular expressions are equal or not ?1) (1+01*0)* 2) 1*(01*0)* 1*Give proper explanation also.
0 votes
0 votes
1 answer
3
Himanshu Goyal asked Jan 28, 2017
622 views
Can someone give me dfa of these Regular Expressions?$0^*(1+0)^*$$0^*(1^++0)^*$Actually i am getting confused between both of them Thanks