Dark Mode

Recent questions tagged dcfl

2 votes

0 answers

1

Can DCFL be ambiguous?
Can DCFL be ambiguous?

h4kr asked in Theory of Computation Feb 2

by h4kr

183 views

1 vote

2 answers

2

DCFL or CFL ?
L = {$a^{n+m}b^{n}a^{m} | n,m \geq 0$} Is the above language DCFL or CFL ?

ggwon asked in Theory of Computation Dec 29, 2022

by ggwon

244 views

0 votes

1 answer

3

could you help me with this made easy question?
I tried to solve but got stuck here.

farmanahmed888 asked in Theory of Computation Dec 14, 2022

by farmanahmed888

197 views

0 votes

1 answer

4

#Self Doubt
L = {0^n 1^2n 0^n+m , n,m>=0} Is this Language CFL or non CFL? According to me we can write this as 0^n 1^n 1^n 0^n 0^m Then we will keep on pushing 0's and as and when we get 1 we keep on popping 0's, now once the stack is ... then on seeing any number of 0's we don't push anything and when we reach the end of the string we simply move to the final state. Is this logic correct?

Sunnidhya Roy asked in Theory of Computation Dec 12, 2022

by Sunnidhya Roy

196 views

0 votes

1 answer

5

TOC | Made Easy Test Series | Q.13
Consider the following statement S: $\left \{ a^{n}b^{n+k}|n\geq 0,k\geq 1 \right \} \cup \left \{a^{n+k}b^{n}|n\geq 0,k\geq 3 \right \}$ is DCFL The above statement is: TRUE FALSE

Souvik33 asked in Theory of Computation Dec 4, 2022

152 views

0 votes

1 answer

6

ME Demo Test Q13
Consider the following statement: S : {$a^{n}b^{n+k} | n\geq 0,k\geq 1$} $\cup$ {$a^{n+k}b^{n} | n\geq 0,k\geq 3$} Which of the following is TRUE about S? (Also explain HOW) S is Regular, but not DCFL S is CFL, but not DCFL S is DCFL, but not Regular None of these

Jaideep Singh asked in Theory of Computation Nov 28, 2022

by Jaideep Singh

115 views

2 votes

1 answer

7

CFL | TOC | Ace Academy Test Series
If L and $L^{c}$ both are CFL, the L must be DCFL a. TRUE b.FALSE

Souvik33 asked in Theory of Computation Nov 23, 2022

122 views

0 votes

1 answer

8

Dcfl union Regular not always dcfl?
$L=\{a^mb^n\mid m≠n\}∪{(a+b)^∗b(b+a)^*a(a+b)^∗}$ $\implies L = \;\{a^mb^n\mid m<n\} \cup \{a^mb^n\mid m>n\} \cup (a+b)^*b(a+b)^*a(a+b)^*$ It is DCFL ∪ Regular, hence it should be DCFL, but not able to design DPDA, always it designed as NPDA. Can anybody make a DPDA for $L$?

juuniversity asked in Theory of Computation Jun 23, 2022

by juuniversity

164 views

1 vote

2 answers

9

DCFL - TOC
Is the following language a DCFL? Please explain your reasoning.

atulcse asked in Theory of Computation Jan 21, 2022

452 views

1 vote

2 answers

10

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

Hirak asked in Theory of Computation May 23, 2019

by Hirak

581 views

1 vote

0 answers

11

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

srestha asked in Theory of Computation Apr 4, 2019

451 views

0 votes

0 answers

12

RL and DCFL
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

Nandkishor3939 asked in Theory of Computation Jan 22, 2019

by Nandkishor3939

374 views

2 votes

3 answers

13

DCFL or CFL?
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 ... 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?

S Ram asked in Theory of Computation Jan 3, 2019

by S Ram

1.6k views

0 votes

1 answer

14

context free grammer
consider following grammer S → aSb / aSbb / aSbbb / ….. is language generated by above grammer is DCFL?

Rahul_Rathod_ asked in Theory of Computation Dec 24, 2018

by Rahul_Rathod_

430 views

0 votes

0 answers

15

Draw PDA for this
L = {a^m b^n c^k=m+n } | m >= 0 and n >= 0 ---------------------- Please draw PDA for this Language!

Guilherme Zanini Mor asked in Theory of Computation Dec 12, 2018

by Guilherme Zanini Mor

460 views

2 votes

1 answer

16

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

srestha asked in Theory of Computation Nov 26, 2018

422 views

1 vote

1 answer

17

DCFL_
state true /false 1) for every DCFL there exist at least one unambiguous grammar

Gurdeep Saini asked in Theory of Computation Nov 22, 2018

by Gurdeep Saini

375 views

0 votes

0 answers

18

own doubt
can we say that every regular language is a DCFL?

sudharshan asked in Theory of Computation Oct 27, 2018

244 views

0 votes

0 answers

19

Concatenation of DCFLs
L1={an bn | n>=0} L2={bn cn | n>=0} What is L1.L2 ? Is it an b2n cn ?

sripo asked in Theory of Computation Oct 13, 2018

by sripo

441 views

0 votes

0 answers

20

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

Na462 asked in Theory of Computation Sep 11, 2018

by Na462

471 views

0 votes

0 answers

21

test series
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

navya n asked in Theory of Computation Sep 3, 2018

407 views

0 votes

0 answers

22

Curiousity
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 ... which is not DCFL Can you write a language which is an intersection between a DCFL and a regular language but not a DCFL.

Vikas Verma asked in Theory of Computation Aug 12, 2018

287 views

0 votes

0 answers

23

Regular language
Whether the language $L=\left \{ a^{n}b^{l}a^{k}:n+l+k> 5 \right \}$ is regular or not???

saumya mishra asked in Theory of Computation Aug 3, 2018

by saumya mishra

190 views

4 votes

2 answers

24

DCFL or Not
$\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?

srestha asked in Theory of Computation Jun 22, 2018

1.2k views

1 vote

1 answer

25

ISRO CS 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 ... ? 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.

Nikhil Patil asked in Theory of Computation Jun 13, 2018

by Nikhil Patil

995 views

0 votes

0 answers

26

regular language and CFL
$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 ... 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

sanju77767 asked in Theory of Computation May 17, 2018

351 views

3 votes

2 answers

27

Concatenation: REG / REC / DCFL / CFL?
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

Tuhin Dutta asked in Theory of Computation Jan 27, 2018

985 views

2 votes

0 answers

28

Union of two DCFL is ?
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

sunil sarode asked in Theory of Computation Jan 19, 2018

by sunil sarode

1.3k views

1 vote

0 answers

29

DCFL01
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

Anjan asked in Theory of Computation Jan 19, 2018

by Anjan

283 views

2 votes

0 answers

30

Intersection of two DCFLs
$ 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$

Tuhin Dutta asked in Theory of Computation Jan 18, 2018

610 views

Page:

1
2
3
next »

Recent questions tagged dcfl