Show that the following program is a nondeterministic acceptor for the set of al

Question

Show that the following program is a nondeterministic acceptor for the set of all non-empty strings (of B's and W's )in which the number of B's equals the number of W's or is twice the number of W's.

For each character in the Input string, put the correspondingly colored ball in the bag.
Pick one Ball and replace it in the bag. If the ball was W GO TO L1. If the ball was B GO TO L2
L1: WHILE there are at least 2 balls in the bag, Pick 2 balls. IF B and W THEN Discard ELSE Put back in bag. EOW (end of while loop)
IF 0 balls THEN HALT ELSE GO TO L1
L2: WHILE there are at least 3 balls in the bag, pick 3 balls. IF 2 B's and one W THEN Discard ELSE Put back in bag. EOW (end of while loop)
IF 0 balls THEN HALT ELSE GO TO L2

Explanation / Answer

since the program needs two while loops and two selecting cases, start the program with a switch case.
here is the pseudo code

"enter B";
Randomize(B); //randomizing the integer ball;
B(0)==W && B(1)==BL //W is white and BL is black;
if(B==W)
{
GOTO L1;
}
if(B==BL)
{
GOTO L2;
}
switch(B);
{

L1:
while(n[i]>=2)
{
n!=0
randomize(n[1]);
randomize(n[2]);
if(n[1]==0&&n[2]==1)
{
for(i=0;i<2;i++)
{
n[i]--; //deleting the elements from the array i.e the bag
}
else()
{
for(i=0;i<2;i++)
{
n[i]++; //putting them back in the bag..
}
n--;
}

L2:

while(n[i]>=3)
{
n!=0
randomize(n[1]);
randomize(n[2]);
randomize(n[3]);
if(n[1]==0&&n[2]==0&&n[3]==1)
{
for(i=0;i<3;i++)
{
n[i]--; //deleting the elements from the array i.e the bag
}
else()
{
for(i=0;i<3;i++)
{
n[i]++;
}
n--;
}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.