The Gateway to Computer Science Excellence
0 votes
L=0^i 1^j 2^k | i=j or j=k

is the grammar DCFG?

in Theory of Computation by Active (5.1k points) | 33 views
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.
Yes i also getting same.
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
by (159 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,585 answers
101,834 users