Computer Science and Engineering

1. State the nullable variables from the following CFG.     SABCa | bD     ABC |b     Bb | ε     CĐ | ε     Dd 2. Write the difference between Pushdown Automata and Turing     Machine. 3. Construct a Turing Machine to accept strings formed with 0 and 1 and having substring 000. 4. Write a short notes on NP complete , NP hard problems 1. Discuss the Pumping lemma for Context Free Languages concept with example {anbncn where n>0}? 2. Construct a Turing Machine to accept the following language.                L = { 0n1n0n | n ≥1} 3. Write a note on Modified PCP and Multi tape Turing machine. 4. Write a short notes on Chomsky hierarchy. 1. Use the following grammar : S à ABC | BbB A à aA | BaC|aaa B à bBb| a|D C à CA|AC D à ⏀ Eliminate ε -productions. Eliminate any unit productions in the resulting grammar. Eliminate any useless symbols in the resulting grammar. Convert the resulting grammar into Chomsky Norma

Write C programs to simulate the Hierarchical  directory File organization technique #include<stdio.h> #include<graphics.h> #include<string.h> struct tree_element { char name[20]; int x, y, ftype, lx, rx, nc, level; struct tree_element *link[5]; }; typedef struct tree_element node; void main() { int gd=DETECT,gm; node *root; root=NULL; create(&root,0,"root",0,639,320); clrscr(); initgraph(&gd,&gm,"c:\tc\BGI"); display(root); closegraph(); } create(node **root,int lev,char *dname,int lx,int rx,int x) { int i, gap; if(*root==NULL) { (*root)=(node *)malloc(sizeof(node)); printf("Enter name of dir/file(under %s) : ",dname); fflush(stdin); gets((*root)->name); printf("enter 1 for Dir/2 for file :"); scanf("%d",&(*root)->ftype); (*root)->level=lev; (*root)->y=50+lev*50; (*root)->x=x; (*root)->lx=lx; (*root)->rx=rx; for(i=0;i<5;i++) (*root)->li

Write C programs to simulate the Two level directory File organization technique #include<string.h> #include<stdlib.h> #include<stdio.h> struct { char dname[10],fname[10][10]; int fcnt; }dir[10]; void main() { int i,ch,dcnt,k; char f[30], d[30]; dcnt=0; while(1) { printf("\n\n1. Create Directory\t2. Create File\t3. Delete File"); printf("\n4. Search File\t\t5. Display\t6. Exit\tEnter your choice -- "); scanf("%d",&ch); switch(ch) { case 1: printf("\nEnter name of directory -- "); scanf("%s", dir[dcnt].dname); dir[dcnt].fcnt=0; dcnt++; printf("Directory created"); break; case 2: printf("\nEnter name of the directory -- "); scanf("%s",d); for(i=0;i<dcnt;i++) if(strcmp(d,dir[i].dname)==0) { printf("Enter name of the file -- "); scanf("%s",dir[i].fname[dir[i].fcnt]); printf("File created"); break; } if(i==dcnt) printf

Write C programs to simulate the Single level directory File organization techniqu #include<stdlib.h> #include<string.h> #include<stdio.h> struct { char dname[10],fname[10][10]; int fcnt; }dir; void main() { int i,ch; char f[30]; dir.fcnt = 0; printf("\nEnter name of directory -- "); scanf("%s", dir.dname); while(1) { printf("\n\n1. Create File\t2. Delete File\t3. Search File \n 4. Display Files\t5. Exit\nEnter your choice -- "); scanf("%d",&ch); switch(ch) { case 1: printf("\nEnter the name of the file -- "); scanf("%s",dir.fname[dir.fcnt]); dir.fcnt++; break; case 2: printf("\nEnter the name of the file -- "); scanf("%s",f); for(i=0;i<dir.fcnt;i++) { if(strcmp(f, dir.fname[i])==0) { printf("File %s is deleted ",f); strcpy(dir.fname[i],dir.fname[dir.fcnt-1]); break; } } if(i==dir.fcnt) printf("File %s not found",f); else dir

//Deadlock   Avoidance Using Bankers Algorithm In C Programming #include<stdio.h> void main() {   int allocated[15][15],max[15][15],need[15][15],avail[15],tres[15],work[15],flag[15];   int pno,rno,i,j,prc,count,t,total;   count=0;   printf("\n Enter number of process:");   scanf("%d",&pno);   printf("\n Enter number of resources:");   scanf("%d",&rno);   for(i=1;i<=pno;i++)   {   flag[i]=0;   }   printf("\n Enter total numbers of each resources:");   for(i=1;i<= rno;i++)   scanf("%d",&tres[i]);   printf("\n Enter Max resources for each process:");   for(i=1;i<= pno;i++)   {   printf("\n for process %d:",i);   for(j=1;j<= rno;j++)    scanf("%d",&max[i][j]);   }   printf("\n Enter allocated resources for each process:");   for(i=1;i<= pno;i++)   {   printf("\n for process %d:",i);