Register

Recent questions tagged context-free-language

2 votes
1 answer
271
Language DCFL?
$L_{1}=\left \{ 0^{m}.1^{n}.2^{m}.3^{n} \right |n,m>0\}$ $L_{2}=\left \{ a^{i}.b^{j}.c^{k}.d^{l} \right |i+k=j+l\}$ which one DCFL? Refrence :https://gateoverflow.in/15327/context-free-or-not I think both not DCFL, but need valid reason for it
$L_{1}=\left \{ 0^{m}.1^{n}.2^{m}.3^{n} \right |n,m>0\}$$L_{2}=\left \{ a^{i}.b^{j}.c^{k}.d^{l} \right |i+k=j+l\}$which one DCFL?Refrence :https://gateoverflow.in/15327/c...
User Avatar
1 votes
3 answers
274
Decidability
Given two deterministic CFG G$_1$ and G$_2$, is L( G$_1$ ) = L( G$_2$ ) ?
Given two deterministic CFG G$_1$ and G$_2$, is L( G$_1$ ) = L( G$_2$ ) ?
User Avatar
0 votes
0 answers
275
Decidability
Given two deterministic CFG G$_1$ and G$_2$ , is L(G$_1$) ∩ L(G$_2$) = ∅ ?
Given two deterministic CFG G$_1$ and G$_2$ , is L(G$_1$) ∩ L(G$_2$) = ∅ ?
User Avatar
1 votes
1 answer
276
Complementation of a Language of a L
If L is any Language and L' be its complement. L is CFL. Which of these two statements is true: 1. For any value of L, L' is not in CFL 2. There exists atleast one value of L for which L' is not in CFL
If L is any Language and L' be its complement. L is CFL. Which of these two statements is true:1. For any value of L, L' is not in CFL2. There exists atleast one value of...
User Avatar
0 votes
1 answer
278
Context Free Grammar
L=0^i 1^j 2^k | i=j or j=k is the grammar DCFG?
L=0^i 1^j 2^k | i=j or j=kis the grammar DCFG?
User Avatar
0 votes
0 answers
280
Ace Book
The complement of the language L containing an equal number of a's , b's and c's is a)regular b)context free c)context sensitive but not context free d)recursive and not a CFL
The complement of the language L containing an equal number of a's , b's and c's isa)regularb)context freec)context sensitive but not context freed)recursive and not a CF...
User Avatar
0 votes
1 answer
282
Theory of Computation
$L1= \left \{ a^m b^n c^n d^m | m \neq n \right \}$ $L2= \left \{a^i b^j c^k | (i<=j)or (j<=i), j=k \right \}$ $L3= \left \{a^i b^j c^k| i=j, j<k \right \}$ The number of the above languages that are context free are ?
$L1= \left \{ a^m b^n c^n d^m | m \neq n \right \}$$L2= \left \{a^i b^j c^k | (i<=j)or (j<=i), j=k \right \}$$L3= \left \{a^i b^j c^k| i=j, j<k \right \}$The number ...
User Avatar
0 votes
0 answers
284
Concatenation of DCFLs
L1={an bn | n>=0} L2={bn cn | n>=0} What is L1.L2 ? Is it an b2n cn ?
L1={an bn | n>=0}L2={bn cn | n>=0}What is L1.L2 ?Is it an b2n cn ?
User Avatar
0 votes
0 answers
286
CFG-Doubt
$L=a^mb^nc^pd^q | m+p=n+q, m,n,p,q>=0$ is the language CFG or CFL?
$L=a^mb^nc^pd^q | m+p=n+q, m,n,p,q>=0$is the language CFG or CFL?
User Avatar
0 votes
0 answers
287
Context free languages
X belongs to {a,b}* such that n(a)<n(b)<2n(a) is a CFL. Please somebody explain the push and pop sequences of the alphabets on the stack. I'm not being able to visualise, how it is CFL?
X belongs to {a,b}* such that n(a)<n(b)<2n(a) is a CFL. Please somebody explain the push and pop sequences of the alphabets on the stack. I'm not being able to visualise,...
User Avatar
0 votes
0 answers
289
DCFL Language
Consider the following languages : L1: {a bn a2n | n ≥ 0 } L2: { a a bn a3n | n ≥ 0 } Which of the following is true ? A. L1 U L2 is regular B. L1 U L2 is DCFL C. L1 intersection L2 is non regular D. L1 U L2 is not CFL
Consider the following languages :L1: {a bn a2n | n ≥ 0 }L2: { a a bn a3n | n ≥ 0 }Which of the following is true ?A. L1 U L2 is regularB. L1 U L2 is DCFLC. L1 inters...
User Avatar
1 votes
0 answers
290
Closure Property
If L1 is CSL and L2 is CFL, then which of the following is correct ? A.L1' - L2 is CSL always B. L1 - L2' is CSL always C. L1 intersection Regular is Regular always D. L1.L2 is CSL but not CFL
If L1 is CSL and L2 is CFL, then which of the following is correct ?A.L1' - L2 is CSL alwaysB. L1 - L2' is CSL alwaysC. L1 intersection Regular is Regular alwaysD. L1.L2...
User Avatar
0 votes
0 answers
291
peter linz
The language L1={a^n b^n} union {b} The language L2={a^n b^n} union {a} They both are deterministic CFL. Am i right?
The language L1={a^n b^n} union {b}The language L2={a^n b^n} union {a}They both are deterministic CFL.Am i right?
User Avatar
0 votes
0 answers
294
PDA-Doubt
L=$a^mb^n$ | m!=n is the following DPDA correct for the mentioned language?
L=$a^mb^n$ | m!=nis the following DPDA correct for the mentioned language?
User Avatar
0 votes
0 answers
295
Doubt-PDA
what is the PDA for {L=$a^mb^n$ |m>n}
what is the PDA for {L=$a^mb^n$ |m>n}
User Avatar
0 votes
1 answer
297
Parsing
For a grammar to be LR(k), it should have a PDA? Like a DPDA or just PDA in general?
For a grammar to be LR(k), it should have a PDA? Like a DPDA or just PDA in general?
User Avatar
2 votes
3 answers
298
TOC self doubt
$\text{Is the language L is DCFL or CFL ?}$
$\text{Is the language L is DCFL or CFL ?}$
User Avatar
1 votes
0 answers
299
DPDA acceptance by empty stack
Is this approach of acceptance by empty stack correct ? I am confused because i have read that acceptance by empty stack may not be able to accept all regular languages.
Is this approach of acceptance by empty stack correct ?I am confused because i have read that acceptance by empty stack may not be able to accept all regular languages.
User Avatar
Page: