search
Log In
0 votes
51 views
L=0^i 1^j 2^k | i=j or j=k

is the grammar DCFG?

in Theory of Computation 51 views
0
No, I don't think so.

Push 0 when you encounter it

Pop 0 when you encounter 1.

Here we lost the track of 'j' so we will not able to compare with 'k' if the first condition(i==j) failed.

But we can construct a NPDA for this.
0
Yes i also getting same.
0
it is non deterministic CFL

1 Answer

0 votes
it is the union of

0^i 1^i 2^k union 0^i 1^j 2^j

so for j is not clear that we r to consider it equal to i or j

NPDA can do that not DPDA

Related questions

0 votes
0 answers
1
105 views
Consider the following CFG 'G' S--> aA/bSS/SS A--> aAb/bAa/AA/ε The language generated by G is: a)Set of all strings with atleast one 'a' b)Set of all strings with atleast two a's c)Set of all strings with atleast one more 'a' than number of b's d)None of these
asked Oct 18, 2018 in Theory of Computation Sambhrant Maurya 105 views
1 vote
1 answer
2
279 views
Please post few examples of Linear Ambiguous Context Free Grammar. It would be helpful if you post grammars for famous languages.
asked Mar 22, 2018 in Theory of Computation Mk Utkarsh 279 views
1 vote
1 answer
3
312 views
Given the Grammar, S -> abB, A -> aaBb, B -> bbAa, A -> ∈ Please explain how we get expression:- L = { ab(bbaa)^n bba (ba)^n / n>= 0 } Please explain step by step.
asked Jul 5, 2017 in Theory of Computation Shubhanshu 312 views
0 votes
1 answer
4
257 views
Do the following productions mean the same Bb->bb and B->b My doubt is that will the first production be used only when we have b in the follow of B or it can be used in any case. If it can be used in any case then will the first production be equal to second production.
asked Apr 4, 2017 in Theory of Computation Srinivas Rao 257 views
...