Register

Formal Languages

• reshown by
377 views
0 votes
0 votes

Consider the language defined as L = { $a^pb^qa^r$ | p = q or q = r} .

L complement is

  1. Regular
  2. CFL but not regular
  3. CSL but not CSL
  4. DCFL
• reshown by
User Avatar

1 Answer

Best answer
1 votes
1 votes
Actually the language L is CFL, and we know that CFL are not closed under Compliment and Intersection.

So compliment of given language will be CSL.
• selected by
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
0 answers
2
Sambhrant Maurya asked Oct 14, 2018
350 views
Formal Languages
Let r1 = (b*ab*ab*ab*)* and r2= (b*ab*ab*)*. What is L(r1) ∩ L(r2)? a) L[b*ab*ab*ab*)*] b) L[b*ab*ab*)*] c) L[b*ab*ab*)6] d) L[b*ab*ab*ab*ab*ab*ab*)*]
Let r1 = (b*ab*ab*ab*)* and r2= (b*ab*ab*)*. What is L(r1) ∩ L(r2)?a) L[b*ab*ab*ab*)*]b) L[b*ab*ab*)*]c) L[b*ab*ab*)6]d) L[b*ab*ab*ab*ab*ab*ab*)*]
User Avatar
0 votes
0 votes
0 answers
3
Sambhrant Maurya asked Oct 14, 2018
464 views
Formal Languages
Let r1= (a+b2)* , r2 = (a* + b*)* , r3 = (a2 + b)* Which of the following is true? a)L(r1) is a subset of L(r2) and L(r3) is a subset of L(r2) b)L(r2) is a subset of L(r1) and L(r2) is a subset of L(r3) c)L(r1) = L(r3) is a subset of L(r2) d) L(r1) U L(r3) = L(r2)
Let r1= (a+b2)* , r2 = (a* + b*)* , r3 = (a2 + b)*Which of the following is true?a)L(r1) is a subset of L(r2) and L(r3) is a subset of L(r2)b)L(r2) is a subset of L(r1) ...
User Avatar
0 votes
0 votes
1 answer
4
Sambhrant Maurya asked Oct 14, 2018
657 views
Formal Languages
If G= ({S} , {a}, {S--->SS} , S), then language L(G) is a)ϕ b)aa(a)* c)(aa)* d)None of these
If G= ({S} , {a}, {S ->SS} , S), then language L(G) isa)ϕb)aa(a)*c)(aa)*d)None of these
User Avatar
Link Copied!