The Gateway to Computer Science Excellence
+17 votes
693 views

Consider the languages 

$L_{1}= \left\{a^{m}b^{n}c^{p} \mid (m = n \vee n = p) \wedge m + n + p \geq 10\right\}$

$L_{2}= \left\{a^{m}b^{n}c^{p} \mid (m = n \vee n = p) \wedge m + n + p \leq 10\right\}$

State which of the following is true?

  1. $L_{1}$ and $L_{2}$ are both regular.
  2. Neither $L_{1}$ nor $L_{2}$ is regular.
  3. $L_{1}$ is regular and $L_{2}$ is not regular.
  4. $L_{1}$ is not regular and $L_{2}$ is regular.
  5. Both $L_{1}$ and $L_{2}$ are infinite.
in Theory of Computation by Boss (30.8k points)
edited by | 693 views
0

Let some language L={ambncp |m=n or n=p} 

L is CFL , not DCFL because either m=n or n=p would create ambiguity so we have to make choices and DCFL can't then handle this.

L2 is finite so regular language //

now here L1is almost L-Land CFL-Regular would be CFL by closure property.

0

Hey @Satbir Can you please help me understand $\mathbf{L_1}$?

0

@ankitgupta.1729

Can you see this one?

2 Answers

+20 votes
Best answer
$L_2$ is finite, so regular.

$L_1$ is non-regular.

(It seems CFL to me as I think it can be implement with the help of PDA , as stack can ensure $(m=n \vee n = p)$ and we can also ensure $(m+n+p \geq 10)$ with minimum states changes along with transitions).

$L_2$ is actually {$c^p$ | $p \leq 10$} $\cup$ {$abc^p$ | $p \leq 8$} $\cup$ {$a^2b^2c^p$ | $p \leq 6$}$\cup$ {$a^3b^3c^p$ | $p \leq 4$} $\cup${$a^4b^4c^p$ | $p \leq 2 $} $\cup${$a^5b^5$}$\cup$ {$a^p$ | $p\leq 10$} $\cup$ {$a^pbc$ | $p\leq 8$} $\cup$ {$a^pb^2c^2$ | $p\leq 6$} $\cup$ {$a^pb^3c^3$ | $p\leq 4$} $\cup$ {$a^pb^4c^4$ | $p\leq 2$} $\cup$ {$b^5c^5$ | $p\leq 10$}

Correct Answer: $D$
by Veteran (57k points)
edited by
0
Sir, Added information :$L_{1}$ will not be a $DCFL$ .right?
0
$L_2$ is regular ..so definitely DCFL too.
0
@Praven sir: sorry i asked about $L_{1}$(edited my comment) which is non-regular.

Will  $L_{1}$ be DCFL? i think its not !
+2
You are right. $L_1$ is NCFL.
0
Hi Praveen Sir,

Can you please give the complement of L2.
0

@Praveen Saini

Is there any other method from the exam point of view?

+1

@`JEET From exam point of view, note that $L_2$ is regular because it is finite. $m + n + p \leq 10$ makes the language finite.

0

Thanks @pritishc

Following a similar logic $\mathbf{L_1}$ is infinite. $\therefore$ Not regular, right or is it like we won't be able to compare the two states?

+1
If a language is finite, it is definitely regular. However, if a language is infinite, it may or may not be regular. $(0 + 1)^*$ is regular, yet infinite. $0^n1^n$ is also infinite, but non-regular.

If there is a pattern in the language that you can exploit, there likely is a DFA/NFA for it. If the language looks like it is non-regular but actually is finite, it is definitely regular and you can make a DFA/NFA for it.

$L_1$ is non-regular because we have to keep track of how many $a$'s vs $b$'s, or $b$'s vs $c$'s, and the language is infinite as well, so we can't create a DFA for it (finite memory of a DFA not equipped to track the counts, would need a stack).
0
Thanks.

Well, this sums up everything.
+9 votes

L1 is CFL

L1={ambnc| (m=n v n=p) ⋀ m+n+p>=10}

Let us say m=n

then L1={anbncp | p>=10-2n}

It cannot be represent in 1 stack . So, it could be CSL

L2={anbncp | p<=10-2n}

it has a finite memory. So it must be regular

Answer will be (D)

by Veteran (119k points)
edited by
0

Praveen Saini plz check this

+1

@Srestha

I think for some finite combination of n and p, p>10-2n.So we can implement that by changing state also.Do we really need another stack for that?

And more over i think L2={ambncp|m=n or n=p} intersection {ambncp|m+n+p>=10} i.e CFL intersection regular..so it would be CFL

Please correct me if i am wrong.

+2

{ambncp|m+n+p>=10} is regular.

How r u saying this?

Can u give a DFA or Regular Expression for it?

+1
<= means there are finite nuber of states.

But >= represents infinite number of states.

So, cannot conclude it with DFA.

yes , you could think about NFA, but m,n,p there are 3 variable also could go any number of times.
0

@srestha L1={ambnc| (m=n v n=p) ⋀ m+n+p>=10} is CFG but L2={ambnc| (m=n v n=p) ⋀ m+n+p<=10} is regular because  has finite length (string always less then 10) show 1 one is cfg but L2 is Regular.

0
should not L1 be csl   not cfl plz correct if i am wrong here
0
Hmmm L1 seems to be CSL because the first part m=n or n=p can be performed by NPDA but this additional counting of m n p cannot be performed in parallel  with one stack..
0

Dear @Praveen Saini @srestha and @KISHALAY DAS

In my view also L1 is CSL

as 

L1={ambnc| (m=n v n=p) ⋀ m+n+p>=10}

Let us say m=n

then L1={anbncp | p>=10-2n}

we can't have value of n after popping out b corresponding to a's so, how we will compare that whether p>=10-2n is right or wrong.

Also, How could we count n using state transition as the core inside CFL also we have finite number of states but here n is not finite.

Please correct me if i am wrong.

Related questions

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,292 answers
198,221 comments
104,908 users