Can someone please suggest a one semester project based on theory of computation of an undergrad level?

It is fine if it is totally theoretical or otherwise.

thank you.

It is pushdown automaton!!

for the PDA:

d=delta

d(q0,a,Z) = {(q0,AZ)}
d(q0,b,Z) = {(q0,BZ)}
d(q0,a,A) = {(q0,AA)}
d(q0,b,A) = {(q0,BA)}
d(q0,a,B) = {(q0,AB)}
d(q0,b,B) = {(q0,BB)}
d(q0,c,Z) = {(q1,Z)}
d(q0,c,A) = {(q1,A)}
d(q0,c,B) = {(q1,B)}
d(q1,a,A) = {(q1,e)}
d(q1,b,B) = {(q1,e)}
d(q1,e,Z0) = {(q1,e)}

the cfg rules are:

S -> [q0 Z q]
[q0 Z q] -> a[q0 A p] [p Z q]
[q0 Z q]-> b[q0 B p] [p Z q]
[q0Aq] -> a[q0Ap] [pAq]
[q0Aq] -> b[q0Bp] [pAq]
[q0Bq] -> a[q0Ap] [pBq]
[q0Bq] -> b[q0Bp] [pBq]
[q0Zq] -> c[q1Zq]
[q0Aq] -> c[q1Aq]
[q0Bq] -> c[q1Bq]
[q1Aq1] -> a
[q1Bq1] -> b
[q1Z0q1] -> e

where p and q can take any of q0 or q1

after removing unnecessary rules we shd get:

S -> [q0Z0q1]
[q0 Z q1] -> a[q0 A q1] [q1 Z q1]
[q0 Z q1] -> b[q0 B q1] [q1 Z q1]
[q0 A q1] -> a[q0 A q1] [q1 A q1]
[q0 A q1] -> b[q0 B q1] [q1 A q1]
[q 0B q1] -> a[q0Aq1] [q1Bq1]
[q0Bq1] -> b[q0Bq1] [q1Bq1]
[q0Zq1] -> c[q1Zq1]
[q0Aq1] -> c[q1Aq1]
[q0Bq1] -> c[q1Bq1]
[q1Aq1] -> a
[q1Bq1] -> b
[q1Zq1] -> e

my question:

of these:
[q0 Z q0] -> a[q0 Aq 0] [q0 Z q0]
[q0 Z q0] -> a[q0 A q1] [q1 Z q0]
[q0 Z q1] -> a[q0 A q0] [q0 Z q1]
[q0 Z q1] -> a[q0 A q1] [q1 Z q1]

only :
[q0 Z q1] -> a[q0 A q1] [q1 Z q1]
is necessary the ...

this prob in no way can be done w/o stack_call[ ] right?
i mean we will always need an extra variable in the stack to indicate which recursion it is.

so the algo:

include "StackOps.h"
include "SortOps.h"

[CODE]
void shell_iter(int t,int n, int h)
{
int i,aux;
Stack stack;
Stack
stackp;
stackp=&stack;
stack=createStack(stack);
while(h>0)
{
while(n>h){
stack=push(stack,n);
n=n-h;
}
while(!isEmpty(stackp))
{
n=pop(stackp);
if (t[n]<t[n-h])
{
aux=t[n];
i=n;
while (i>=h && aux<t[i-h]){
t[i]=t[i-h];
i=i-h;
}
t[i]=aux;
}
}
h=h/3;
}
}[/CODE]

is flawed right?
this algo does not wrk i suppose. please confirm and let me know.

thank you Narue!!
you are a true code goddess!! \m/

remove the recursive call assuming stack operations push pop etc are given
I dont know how to deal with the for loop here

I have the following code for shell sort (recursive) given in the question
where t[ ] is an array to be sorted, n=no of elements initially. h is any large no initially,say h>n.
[CODE]void shell_rec(int t[],int n,int h)
{
int aux,i;
if(h<=0)
return;

if(n>h)
{   shell_rec(t,n-h,h);
    if(t[n]<t[n-h])
    {
        aux=t[n];
        i=n;
           for(i=n;i>=h && aux<t[i-h];i=i-h)
            t[i]=t[i-h];
        t[i]=aux;
    }
}

shell_rec(t,n,h/3);

}[/CODE]

removing tail recursion i get:

[CODE]void shell_rec(int t[],int n,int h)
{
int aux,i;
int j;
for(j=h;j>0;j=j/3)
{
if(n>j)
{ shell_rec(t,n-j,j);
if(t[n]<t[n-j])
{
aux=t[n];
i=n;
for(i=n;i>=j && aux<t[i-j];i=i-j)
t[i]=t[i-j];
t[i]=aux;
}
}
}
}[/CODE]

now i want to remove the recursion using explicit stack
pls help!

[QUOTE]if you sort it DESCENDING you can loop through the array subbing the element from the total sum, if the next element causes the result to fall below zero you skip it for example[/QUOTE]

what if u have:
sum=14
integers : 10 5 -1

then it gives false that sum of 14 cannot be got!

because 14-10=4
4-5 = -1
hence return false

but 10+5-1=14

@jnawrocki:

but I donot want p to change when I change i

So then how do I store the value of a variable in another variable that is pointed to by a pointer? in other words how do i change the value stored at *n to the value of m?
(and I dont want n to point to the same address as that of m... i.e. change in one should not effect the other)

I did go through the link eternallyconfuzzled ( an excellent tutorial on trees I must say that I had been following even before it (the link) was posted here) but could not find the answer and the "correct" way to do so.

the point is the code that I posted gives an error
why?

and somtimes the other exp gives an error...
is it compiler dependent? I used GNU gcc compiler and the code is in c(not c++)

please help me understand when does one use
*n=m

and
when to use

  n=&m

[code]int n,m;
n=5;
m=2;
*n=m;[/code]

//gives an error