menu
search
Log In
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

Subjects

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

test series

0 votes
146 views
L1 = {a^mb^nc^p | m ≥ n or n = p}
L2 = {a^mb^nc^p | m ≥ n and n = p}

(a) Both are NCFL’s
(b) L1 is DCFL and L2 is NCFL
(c) L1 is NCFL and L2 is not context-free
(d) Both are not context-free
Solution: Option (c)

how it is possible plz explain indetail
in Theory of Computation
edited by 146 views
0
Option c and d are same right? :o
0
nope
0
Both the options say that they L1 and L2 are ncfls.
0
option c says L1 is non determinstic context free language and L2 is determinstic cfl

option d says both L1 and L2 are non cfl
0
L1 NCFL

L2 CSL
0
plz explain brifely
0

@navya n

L1 requires only one comparission at a time ===>CFL, due to Ambiguity it is Non-Deterministic CFL

L2 requires two comparissions at a time ===> CSL

0
Oh yes..sorry .I read it wrongly..

Option C says L1 is ncfl and L2 is not CFL
0
How L1 becomes NCFL? can anybody give PDA for it?
1

There are two possibilities

1) m>=n                                  2) n=p

For 1) first push a then pop 1 a for each b. Since m>=n so it might happen that there are still some a's left after all b's are exhausted.

 For the remaining c's we don't need to do anything

For 2) Do nothing when we get a and push all b's and pop each b for each c.

 

 

1
Thanks @MNIPanda, I really appreciate your help.

Please log in or register to answer this question.

← Prev. Next →
← Prev. Qn. in Sub. Next Qn. in Sub. →

Related questions

1 vote
0 answers
1
175 views
Made Easy Test Series : Doubt on Automata
$\left \{ a^{n}.b^{n+k}\mid n\geq 0,k\geq 1 \right \}\cup \left \{ a^{n+k}.b^{n}\mid n\geq 0,k\geq 3 \right \}$ is DCFL Is it true? As we know union of two DCFL cannot be DCFL
$\left \{ a^{n}.b^{n+k}\mid n\geq 0,k\geq 1 \right \}\cup \left \{ a^{n+k}.b^{n}\mid n\geq 0,k\geq 3 \right \}$ is DCFL Is it true? As we know union of two DCFL cannot be DCFL
asked Apr 4, 2019 in Theory of Computation srestha 175 views
5 votes
1 answer
2
316 views
TOC Test Series
Consider the languages (I) L1= {w#x , where w,x ∈ (0+1)* and # is a special character and w is a prefix of x } . (II) L2={w#x , where w,x ∈ (0+1)* and # is a special character and wR, is a prefix of x}. (III) L3={w#x , where w,x ∈ (0+1)* and # is a ... (II) and (III) is DCFL (I) and (IV) is recursive but not CFL. (I) is recursive , (II) is DCFL , (III) and (IV) are CFL but not DCFL
Consider the languages (I) L1= {w#x , where w,x ∈ (0+1)* and # is a special character and w is a prefix of x } . (II) L2={w#x , where w,x ∈ (0+1)* and # is a special character and wR, is a prefix of x}. (III) L3={w#x , where w,x ∈ (0+1)* and # is a special ... CFL. (II) and (III) is DCFL (I) and (IV) is recursive but not CFL. (I) is recursive , (II) is DCFL , (III) and (IV) are CFL but not DCFL
asked Oct 14, 2017 in Theory of Computation sunil sarode 316 views
0 votes
1 answer
4
277 views
ACE Academy: Recognition of CFG
$L1 =\left \{ a^{m} b^{n} c^{p} | \left ( m \geq n \right )\text{or} \left ( n = p \right ) \right \}$ $L2 =\left \{ a^{m} b^{n} c^{p} | \left ( m \geq n \right )\text{and} \left ( n = p \right ) \right \}$ $(a)$ Both are NCFL’s $(b)$ L1 is DCFL and L2 is NCFL $(c)$ L1 is NCFL and L2 is not context-free $(d)$ Both are not context-free
$L1 =\left \{ a^{m} b^{n} c^{p} | \left ( m \geq n \right )\text{or} \left ( n = p \right ) \right \}$ $L2 =\left \{ a^{m} b^{n} c^{p} | \left ( m \geq n \right )\text{and} \left ( n = p \right ) \right \}$ $(a)$ Both are NCFL’s $(b)$ L1 is DCFL and L2 is NCFL $(c)$ L1 is NCFL and L2 is not context-free $(d)$ Both are not context-free
asked May 23, 2019 in Theory of Computation Hirak 277 views
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...