{${a^mb^nc^k|if \;k=even \;then\; m=n}$}

we can write this as

{$a^nb^nc^{2i}|i,n>=0$}$\cup$ {$a^jb^kc^{2i+1}|i,j,>=0$} we can clearly see that L1 is DCFL ,we can write like this also for 2nd ,so both are DCFL

The Gateway to Computer Science Excellence

+1 vote

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 the answer 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?

0

Let's check for first

{${a^mb^nc^k|if \;k=even \;then\; m=n}$}

we can write this as

{$a^nb^nc^{2i}|i,n>=0$}$\cup$ {$a^jb^kc^{2i+1}|i,j,>=0$} we can clearly see that L1 is DCFL ,we can write like this also for 2nd ,so both are DCFL

{${a^mb^nc^k|if \;k=even \;then\; m=n}$}

we can write this as

{$a^nb^nc^{2i}|i,n>=0$}$\cup$ {$a^jb^kc^{2i+1}|i,j,>=0$} we can clearly see that L1 is DCFL ,we can write like this also for 2nd ,so both are DCFL

0

@Prateek Raghuvanshi so you have considered union of two DCFL as DCFL ?? or is it about deterministic children ??

0

Actually we can design dpda ,as we can see in second part of union there is no comparison and in first one there is comparison so design dpda for first one and for second one just skip all .this can be done by dpda .

0

Hello, But Union of 2 DCFL is not DCFL.

According to you how in same state we can push or pop for input as well as just read and skip for that also ?

According to you how in same state we can push or pop for input as well as just read and skip for that also ?

0

Dcfl under union is not closed ,it doesn't mean that it never be dcfl right. It means that union of dcfl may or may not dcfl but in this case it is dcfl .I will show you dpda

0

@s ram

P: k is even

Q: m=n

Given, P->Q which can also be written as

Q'->P'

So now we can check for the number of A's and B's and depending on their inequality we can take decision.

If unequal i.e. Q'=T we have to ensure P' is T I.e. C's are odd.

Else if equal then C's can be anything

P: k is even

Q: m=n

Given, P->Q which can also be written as

Q'->P'

So now we can check for the number of A's and B's and depending on their inequality we can take decision.

If unequal i.e. Q'=T we have to ensure P' is T I.e. C's are odd.

Else if equal then C's can be anything

0

assume it is L$, then it is just like

push a's for each a, pop a for each b,

if more b's than a, then just push b on to the stack.

on k just changes the states ( even = one state and odd for another state )

if $ appear on even state, go to reject !

else $ appear on odd state, accept it !

else accept ( i mean number of a's = number of b's then no need to check k's even or not, but take care of dead conditions. )

EDIT :- i hope you also did the same !

+1

@MiNiPanda Nicely explained.. actually solving recursively i was messed up somehow.. and could not build DPDA hence got confused. but now all is as clear as class...Thank u... @MiNiPanda @Prateek Raghuvanshi

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,367 answers

198,500 comments

105,271 users