flat qp


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 Normal Form
2. Write a short notes on universal Turing machine
3.Write short notes on posts corresponding problem and check the following is PCP or not
I
A
B
1
11
111
2
100
001
3
111
11

                       4. Write short notes on Chomsky hierarchy and NP complete problems?

Comments

Post a Comment

Popular posts from this blog

Write C programs to simulate the Paging techniques of memory management

Image
#include<stdio.h> #define MAX 50 int main() { int page[MAX],i,n,f,ps,off,pno; int choice=0; printf("\nEnter the no of  peges in memory: "); scanf("%d",&n); printf("\nEnter page size: "); scanf("%d",&ps); printf("\nEnter no of frames: "); scanf("%d",&f); for(i=0;i<n;i++) page[i]=-1; printf("\nEnter the page table\n"); printf("(Enter frame no as -1 if that page is not present in any frame)\n\n"); printf("\npageno\tframeno\n-------\t-------"); for(i=0;i<n;i++) { printf("\n\n%d\t\t",i); scanf("%d",&page[i]); } do { printf("\n\nEnter the logical address(i.e,page no & offset):"); scanf("%d%d",&pno,&off); if(page[pno]==-1) printf("\n\nThe required page is not available in any of frames"); else printf("\n\nPhysical address(i.e,frame no & offset):%d,%d",page[pno],off); prin...
Read more

Write C programs to simulate the Two level directory File organization technique

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...
Read more

Write C programs to simulate the Single level directory File organization techniqu

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...
Read more