Recent questions tagged dcfl

1
Which of the following statement is true? Deterministic context free language are closed under complement. Deterministic context free language are not closed under Union. Deterministic context free language are closed under intersection with regular set. All of the options
2
$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
1 vote
3
$\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
4
the answer is given that the statement 2 is correct? But how… even if we create a DCFL by final state condition like : q(b,z0| z0)-→ final state ,q(null,a|z0) ----→ final state [Thats what was mentioned in the video solution] it will accept the string aab
1 vote
5
Given that: { A^m B^n C^k/ if (k=even) then m=n} { A^m B^n C^k/ if (n=even) then m=k} Which of the above languages are DCFL? According to me it is CFL as we have to first count k and then compare other inputs.. same for second language but ... given is both are DCFL? it is only possible if skip path is exists here? does it exist for DCFLs? so confused please guide me? if given answer is correct?
6
consider following grammer S → aSb / aSbb / aSbbb / ….. is language generated by above grammer is DCFL?
7
L = {a^m b^n c^k=m+n } | m >= 0 and n >= 0 ---------------------- Please draw PDA for this Language!
1 vote
8
$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
1 vote
9
state true /false 1) for every DCFL there exist at least one unambiguous grammar
10
can we say that every regular language is a DCFL?
11
L1={an bn | n>=0} L2={bn cn | n>=0} What is L1.L2 ? Is it an b2n cn ?
12
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
13
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
14
In an intersection between a regular language and a DCFL, we always tend to promote regular language to DCFL and say that the result will be intersection between DCFL and DCFL but since DCFLs are not closed under intersection we say the result will be a CFL. But I feel ... DCFL which is not DCFL Can you write a language which is an intersection between a DCFL and a regular language but not a DCFL.
15
Whether the language $L=\left \{ a^{n}b^{l}a^{k}:n+l+k> 5 \right \}$ is regular or not???
16
$\left \{ a^{m+n}b^{m+n}c^{n}|m,n\geq 1 \right \}$ $\left \{ a^{m+n}b^{m+n}c^{k} |m,n,k\geq 1\right \}$ $\left \{ a^{m+n}b^{m+k}c^{n+k} |m,n,k\geq 1\right \}$ Which one DCFL, CFL or CSL?
1 vote
17
Consider the following statements about the context free grammar G = {S-->SS , S-->ab , S-->ba , S-->^} I. G is ambiguous II. G produces all strings with equal number of a’s and b’s III. G can be accepted by a deterministic PDA. Which combination below expresses all the true statements about ? A) I only B) I and III C) II and II D) All I,II,III In a answer key shown answer D but II is not right.
18
$L=\left \{ a^{n}b^{n}c^{n}d^{n} | n<10^{10} \right \}$ I know this language is regular language so it is DCFL AND CFL also but how can we implenment this language with DCFL with stack because till we reach c there will be nothing in ... with this language can be implemented using FA We can have these many states to compare how we will compare in stack explain the logic of this language with DCFL
19
Let A is the language where no of 'a' is greater than no of 'b' and B is the language where no of 'b' is greater than no of ‘a’ the language A.B is ______________ a. Regular b. DCFL but not Regular c. CFL but not DCFL d. REC but not DCFL
20
Consider two languages LA and LB over Σ={a,b}. LA= {a^ib^ja^k | i,j,k ≥ 0 and j=i+k} LB= {b^ia^jb^k | i,j,k ≥ 0 and j=i+k} Then ( LA ∪ LB ) is : A DCFL but not regular B CFL but not DCFL C None of the above D CSL but not CFL
1 vote
21
What is DCFL U Regular ? Every Regular lang is DCFL , That means DCFL U DCFL = not DCFL ? since DCFL's are not closed under union
22
$L_1\ =\ \{ \ a^mb^mb^na^n | m,n\ >\ 0\}\\ L_2\ =\ \{ \ a^mb^na^nb^m | m,n\ >\ 0\}$ Find $L_1 \cap L_2$
23
Can Anyone please explain the difference between DCFL and NDCGL with 4-5 good and tricky,complex examples.
24
Not able to understand whether it is CFL or not due to the condition 'm>=481'.
1 vote
25
$L1 = \bigl\{a^mb^nc^pd^q \mid m+q = n+p \bigr\}$ $L2 = \bigl\{a^mb^nc^pd^q \mid m+p = n+q \bigr\}$ 1. L1 is DCFL, L2 is not 2. L2 is DCFL, L1 is not 3. Both are not DCFL 4. Both are DCFL
26
27
Consider the following languages: L1={abna2n|n>=0} L2={aabna3n|n>=0} Why L1UL2 is DCFL please explain?
1 vote
Hi Guys, What will be ${\left ( DCFL \cup Regular \right )} '$ ?