Dark Mode

Recent questions tagged dcfl

1 vote

1 answer

1

Is it DCFL or CFL?
If it’s DCFL then also construct the DPDA ?

vedantk asked in Theory of Computation Jan 10

143 views

0 votes

0 answers

2

Can
Can $\Sigma^{*}$ be called DCFL? If yes, what would the state transition diagram of its PDA look like?

raj_uddeshya157 asked in Theory of Computation Dec 27, 2023

by raj_uddeshya157

68 views

2 votes

0 answers

3

Can DCFL be ambiguous?
Can DCFL be ambiguous?

h4kr asked in Theory of Computation Feb 2, 2023

by h4kr

457 views

1 vote

2 answers

4

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

705 views

0 votes

1 answer

5

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

394 views

0 votes

1 answer

6

#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

598 views

1 vote

1 answer

7

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

338 views

0 votes

1 answer

8

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

285 views

2 votes

1 answer

9

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

311 views

0 votes

1 answer

10

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 22, 2022

by juuniversity

340 views

1 vote

2 answers

11

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

atulcse asked in Theory of Computation Jan 21, 2022

697 views

1 vote

2 answers

12

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 22, 2019

by Hirak

788 views

1 vote

0 answers

13

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

668 views

0 votes

0 answers

14

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

479 views

2 votes

3 answers

15

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

2.0k views

0 votes

1 answer

16

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_

574 views

0 votes

0 answers

17

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

527 views

2 votes

1 answer

18

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

564 views

1 vote

1 answer

19

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

556 views

0 votes

0 answers

20

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

sudharshan asked in Theory of Computation Oct 27, 2018

386 views

0 votes

0 answers

21

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

594 views

0 votes

0 answers

22

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

711 views

0 votes

0 answers

23

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

656 views

0 votes

0 answers

24

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

376 views

0 votes

0 answers

25

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

257 views

4 votes

2 answers

26

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.6k views

1 vote

1 answer

27

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

1.2k views

0 votes

0 answers

28

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

432 views

3 votes

2 answers

29

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

1.2k views

2 votes

0 answers

30

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.7k views

Page:

1
2
3
next »

Recent questions tagged dcfl