Register

TOC, RL

960 views
1 votes
1 votes
Consider the following language L = {w ∈ (a+b)* | w has atleast as many occurrences of (bba)’s as (abb)’s}. Which of the following statements is/are true?
S1: Language L is regular.
S2: Complement of L is CFL.
S3: Complement of L is CSL.
S4: Reversal of L is CFL.
User Avatar

2 Answers

2 votes
2 votes
there is no need to keep the number of bba’s in the memory because whenever two abb’s comes together (adjacent), then one bba’s always come between them. So  L is regular.  regular language is closed under complement, reversal and regular language are subset of CSL and CFL.
So, all the statements are correct.
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
1 answer
1
manisha11 asked Aug 10, 2018
1,252 views
TOC, RL
Consider the following S1: Pumping lemma is used to prove, that particular language is not regular S2: For all DCFL there exist LR(k) grammar but LL(k) may not exist. Which of the above statements are true? (a) Only S1 (b) Only S2 (c) Only S1 and S2 (d) None of these
Consider the followingS1: Pumping lemma is used to prove, that particular language is not regularS2: For all DCFL there exist LR(k) grammar but LL(k) may not exist.Which ...
User Avatar
1 votes
1 votes
0 answers
2
ck asked Jul 22, 2017
312 views
TOC RL
If we number sigma* in dictionary order then sigma* is countable infinite. On the other hand sigma* is the superset of all the lunguages so is sigma* regular?
If we number sigma* in dictionary order then sigma* is countable infinite. On the other hand sigma* is the superset of all the lunguagesso is sigma* regular?
User Avatar
0 votes
0 votes
1 answer
4
ck asked Jun 23, 2017
770 views
TOC RL and FA
Is every EPSILON-NFA a DFA given the fact that every NFA is a DFA and every NFA is EPSILON-NFA
Is every EPSILON-NFA a DFA given the fact that every NFA is a DFA and every NFA is EPSILON-NFA
User Avatar
Link Copied!