The Gateway to Computer Science Excellence
+2 votes
Identify the language :

L1={ a^p b^q c^r  /   p<=q}

L2 = {a^p b^q c^r  /   p>q }

L3 = {a^p b^q c^r  /  q = r } where p ,q,r >= 0

then { L1 U L2 U L3 }  is

A. regular

B.CFl but not Dcfl

C. Cfl
in Theory of Computation by Active (3.2k points) | 112 views
Regular ??
ya answer is regular  but how can it be regular .. L1 U L2 is P*q* still  one comparision is there that is   q=r . that says no of b should be equal to no of c . explain it
L1 and L2 has all possible combinations of p,q and r. Which will also have q=r.
L1 and L2 removes bounding between p and q. Because L1 has lesser p than q and L2 has more p, so overall any number of p and q possible. And im L1 and L2 itself there is no restriction on r, so q=r comprises into that directly.

hence language will be $a^pb^qc^r / p,q,r \geq 0$

2 Answers

+1 vote
Best answer

(a*b*c*) U (a*bqcr  | q=r ) = Regular . 

by Active (2k points)
selected by
first part is regular but second part after OR is cfl .. we can not ignore 1 comparison is there that is number of b should be equal to c . so a/c to me its CFL.

a*b* union an bn = a*b* hope you get it.

you mean a*b*c* U a*b^nc^n   yeah its regular,it was really a silly one :( that i asked.  thank you .
understand  in betterway the closure property of regular expression and cfl
0 votes

in first expression condition only on p and q not on r which is p<=q and second expression condition only on pand q not on r which is p>q if we take union of exp1 and exp2 then  then the value possible to p and q is whole natural number  and third expression condition will also be lie in this union expression means regular expression for this union is a*b*c*

by Junior (909 points)

No related questions found

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,366 answers
105,265 users