search
Log In

Recent questions tagged dcfl

0 votes
5 answers
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
asked Mar 30 in Theory of Computation Lakshman Patel RJIT 60 views
0 votes
1 answer
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
asked May 23, 2019 in Theory of Computation Hirak 176 views
1 vote
0 answers
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
asked Apr 4, 2019 in Theory of Computation srestha 120 views
0 votes
0 answers
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
asked Jan 22, 2019 in Theory of Computation Nandkishor3939 63 views
1 vote
0 answers
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?
asked Jan 3, 2019 in Theory of Computation S Ram 351 views
0 votes
0 answers
6
consider following grammer S → aSb / aSbb / aSbbb / ….. is language generated by above grammer is DCFL?
asked Dec 24, 2018 in Theory of Computation Rahul_Rathod_ 113 views
0 votes
0 answers
7
1 vote
1 answer
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
asked Nov 26, 2018 in Theory of Computation srestha 147 views
1 vote
1 answer
9
state true /false 1) for every DCFL there exist at least one unambiguous grammar
asked Nov 22, 2018 in Theory of Computation Gurdeep Saini 101 views
0 votes
0 answers
10
can we say that every regular language is a DCFL?
asked Oct 27, 2018 in Theory of Computation sudharshan 71 views
0 votes
0 answers
11
0 votes
0 answers
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
asked Sep 11, 2018 in Theory of Computation Na462 136 views
0 votes
0 answers
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
asked Sep 3, 2018 in Theory of Computation navya n 96 views
0 votes
0 answers
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.
asked Aug 12, 2018 in Theory of Computation Vikas Verma 123 views
0 votes
0 answers
15
Whether the language $L=\left \{ a^{n}b^{l}a^{k}:n+l+k> 5 \right \}$ is regular or not???
asked Aug 3, 2018 in Theory of Computation saumya mishra 66 views
3 votes
1 answer
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?
asked Jun 22, 2018 in Theory of Computation srestha 399 views
1 vote
1 answer
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.
asked Jun 13, 2018 in Theory of Computation Nikhil Patil 284 views
0 votes
0 answers
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
asked May 17, 2018 in Theory of Computation sanju77767 167 views
3 votes
2 answers
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
asked Jan 27, 2018 in Theory of Computation Tuhin Dutta 299 views
2 votes
0 answers
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
asked Jan 19, 2018 in Theory of Computation sunil sarode 453 views
1 vote
0 answers
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
asked Jan 19, 2018 in Theory of Computation Anjan 67 views
2 votes
0 answers
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$
asked Jan 18, 2018 in Theory of Computation Tuhin Dutta 198 views
2 votes
0 answers
23
Can Anyone please explain the difference between DCFL and NDCGL with 4-5 good and tricky,complex examples.
asked Jan 13, 2018 in Theory of Computation ankit_thawal 40 views
2 votes
3 answers
24
1 vote
2 answers
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
asked Dec 21, 2017 in Theory of Computation atul_21 211 views
0 votes
0 answers
26
0 votes
1 answer
27
Consider the following languages: L1={abna2n|n>=0} L2={aabna3n|n>=0} Why L1UL2 is DCFL please explain?
asked Dec 2, 2017 in Theory of Computation shivangi5 316 views
1 vote
2 answers
28
Hi Guys, What will be ${\left ( DCFL \cup Regular \right )} '$ ?
asked Nov 11, 2017 in Theory of Computation Chhotu 283 views
6 votes
1 answer
29
Consider the follwoing Language L1= {0n1*0n | n>0} is DCFL or Not? L2= {0n1+0n | n>0} is DCFL or Not?
asked Nov 4, 2017 in Theory of Computation Anu007 242 views
5 votes
1 answer
30
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 175 views
...