Theory of Automata and Formal
Download 1.49 Mb.
|
1 2
AUTOMATAEPERIMENTS|
A Lab File On Theory of Automata and Formal Languages (BCSP 405) Submitted for Bachelor of Technology In Computer Science and Engineering Women Institute of Technology (Department of Computer Science and Engineering) Submitted to- Submitted by- Mrs. Rekha Rani Name:-Shivani Bhatt Assistant Professor Year/Sem:-2nd/4th (H.O.D- C.S.E Department) Roll no. 691230101016 Session:-Feb-May 2020 INDEX
EXPERIMENT NO.1 AIM: Design a Program for creating machine that accepts three consecutive one. Source code: #include #include #include void main(){ inti,counter=0; charstr[20]; clrscr(); printf("Enter a string of 0's and 1's:\n"); scanf("%s", &str); for(i=0;i { if(str[i]=='1') { counter++; if(counter==3) break; } else{ counter=0; } } if(counter==3) printf("The string is accepted"); else printf("The string is rejected"); getch(); } OUTPUT:- DFA: EXPERIMENT NO.2 AIM:Design a Program for creating machine that accepts the string always ending with 101. SOURCE CODE: #include #include #include void main() { intlen; charstr[20]; clrscr(); printf("Enter a string\n"); scanf("%s", &str); len= strlen(str); if(str[len-3]=='1'&&str[len-2]=='0'&&str[len-1]=='1') printf("The string is accepted"); else printf("The string is rejected"); getch(); } OUTPUT: DFA: EXPERIMENT NO.3 AIM: Design a program for Mode 3 machine. SOURCECODE:- #include #include #include int convert(long n); void main() { long n; int dec; clrscr(); printf("Enter a binary number: "); scanf("%lld", &n); dec = convert(n); if(dec%3 == 0) { printf("It is divisible by 3"); } else { printf("It is not divisible by 3"); } getch(); } int convert(long n) { int dec = 0, i = 0, rem; while (n != 0) { rem = n % 10; n /= 10; dec += rem * pow(2, i); ++i; } return dec; } OUTPUT:- DFA:- EXPERIMENT NO.4 AIM: Design a program for Mode 3 machine. INPUT : Enter the decimal number PROCEDURE: Consider the transition function F(p,x)=q.It tells that reading on alphabet x,we move from state p to state q .Let us name the states as 0,1,2.The initial state will always be zero.The final state indicates the remainder.If final state is zero then number is divisible. SOURCE CODE: #include #include #include void preprocess(int k, int Table[][2]) { int trans0, trans1,sta for ( state=0; state { trans0 = state<<1; Table[state][0] = (trans0 < k)? trans0: trans0-k; trans1 = (state<<1) + 1; Table[state][1] = (trans1 < k)? trans1: trans1-k; } } void isDivisibleUtil(int num, int* state, int Table[][2]) { if (num != 0) { isDivisibleUtil(num>>1, state, Table); *state = Table[*state][num&1]; } } int isDivisible (int num, int k) { int (*Table)[2] = (int (*)[2])malloc(k*sizeof(*Table)); preprocess(k, Table); int state = 0; isDivisibleUtil(num, &state, Table); return state; } int main() { int num = 40; int k = 2; int remainder = isDivisible (num, k); if (remainder == 0) printf(“Divisible\n”); else printf(“Not Divisible: Remainder is %d\n”, remainder); return 0; } OUTPUT: EXPERIMENT NO.5 AIM:- Design a program for creating a machine which accepts string having equal number of 1’s and 0’s. SOURCE CODE:- #include #include int main() { int l=1000; char* s= malloc(l*sizeof(char)); printf("Enter string: "); fgets(s, sizeof(s), stdin); int i; int count0=0, count1=0; for(i=0;s[i]!='\0';i++){ if(s[i]=='0'){ count0++; } if(s[i]=='1'){ count1++; } } if(count1==count0){ printf("String entered is accepted"); } else{ printf("String entered is rejected"); } return 0; } OUTPUT:- EXPERIMENT NO.6 AIM:- Design a program for creating a machine which counts number of 1’s and 0’s in given string. SOURCE CODE:- #include #define INT_SIZE sizeof(int) * 8 int main() { int num, zeros, ones, i; printf("Enter any number: "); scanf("%d", &num); zeros = 0; ones = 0; for(i=0; i { if(num & 1) ones++; else zeros++; num >>= 1; } printf("Total zero bit is %d\n", zeros); printf("Total one bit is %d", ones); return 0; } OUTPUT:- EXPERIMENT NO.7 AIM:Design a program to find two’s complement of a given binary number. INPUT:Enter the 8 bit binary number PROCEDURE: Enter 8 bit binary number.For example let the binary number whose two’s complement we have to find is 01101100.to find twos complement,simply invert each bit of given binary number ,which will be 10010011.Then add 1 to the LSB of this result that is 10010011+1=10010100. SOURCE CODE: #include #define SIZE 8 int main() { char binary[SIZE + 1], onesComp[SIZE + 1], twosComp[SIZE + 1]; int i, carry=1; printf(“Enter %d bit binary value: “, SIZE); gets(binary); for(i=0; i { if(binary[i] == ‘1’) { onesComp[i] = ‘0’; } else if(binary[i] == ‘0’;) { onesComp[i] = ‘1’; } } onesComp[SIZE] = ‘\0’; for(i=SIZE-1; i>=0; i--) { if(onesComp[i] == ‘1’&& carry == 1) { twosComp[i] = ‘0’; } else if(onesComp[i] == ‘0’&& carry == 1) { twosComp[i] = ‘1’; carry = 0; } else { twosComp[i] = onesComp[i]; } } twosComp[SIZE] = ‘\0’; printf(“Original binary = %s\n”, binary); printf(“Ones complement = %s\n”, onesComp); printf(“Twos complement = %s\n”, twosComp); return 0; } OUTPUT: EXPERIMENT NO.8 AIM:- Design a program which will increment a given number by one. SOURCE CODE:- #include int addOne(int x) { int m = 1; while( x & m ) { x = x ^ m; m <<= 1; } x = x ^ m; return x; } int main() { printf("%d", addOne(13)); getchar(); return 0; OUTPUT:- EXPERIMENT NO.9 AIM:Design a program to convert NDFA to DFA. PROCEDURE: Suppose there is an NFA N < Q, ∑, q0, δ, F > which recognizes a language L. Then the DFA D < Q’, ∑, q0, δ’, F’ > can be constructed for language L as: Step 1: Initially Q’ = ɸ. Step 2: Add q0 to Q’. Step 3: For each state in Q’, find the possible set of states for each input symbol using transition function of NFA. If this set of states is not in Q’, add it to Q’. Step 4: Final state of DFA will be all states with contain F (final states of NFA) SOURCE CODE: #include #include #include int ninputs; int dfa[100][2][100] = {0}; int state[10000] = {0}; char ch[10], str[1000]; int go[10000][2] = {0}; int arr[10000] = {0}; int main() { int st, fin, in; int f[10]; int i,j=3,s=0,final=0,flag=0,curr1,curr2,k,l; int c; printf(“\nFollow the one based indexing\n”); printf(“\nEnter the number of states::”); scanf(“%d”,&st); printf(“\nGive state numbers from 0 to %d”,st-1); for(i=0;i state[(int)(pow(2,i))] = 1; printf(“\nEnter number of final states\t”); scanf(“%d”,&fin); printf(“\nEnter final states::”); for(i=0;i { scanf(“%d”,&f[i]); } int p,q,r,rel; printf(“\nEnter the number of rules according to NFA::”); scanf(“%d”,&rel); printf(“\n\nDefine transition rule as \”initial state input symbol final state\”\n”); for(i=0; i { scanf(“%d%d%d”,&p,&q,&r); if (q==0) dfa[p][0][r] = 1; else dfa[p][1][r] = 1; } printf(“\nEnter initial state::”); scanf(“%d”,&in); in = pow(2,in); i=0; printf(“\nSolving according to DFA”); int x=0; for(i=0;i { for(j=0;j<2;j++) { int stf=0; for(k=0;k { if(dfa[i][j][k]==1) stf = stf + pow(2,k); } go[(int)(pow(2,i))][j] = stf; printf(“%d-%d-->%d\n”,(int)(pow(2,i)),j,stf); if(state[stf]==0) arr[x++] = stf; state[stf] = 1; } } for(i=0;i { printf(“for %d ---- “,arr[x]); for(j=0;j<2;j++) { int new=0; for(k=0;k { if(arr[i] & (1< { int h = pow(2,k); if(new==0) new = go[h][j]; new = new | (go[h][j]); } } if(state[new]==0) { arr[x++] = new; state[new] = 1; } } } printf(“\nThe total number of distinct states are::\n”); printf(“STATE 0 1\n”); for(i=0;i<10000;i++) { if(state[i]==1) { int y=0; if(i==0) printf(“q0 “); else for(j=0;j { int x = 1< if(x&i) { printf(“q%d “,j); y = y+pow(2,j); } } printf(“ %d %d”,go[y][0],go[y][1]); printf(“\n”); } j=3; while(j--) { printf(“\nEnter string”); scanf(“%s”,str); l = strlen(str); curr1 = in; flag = 0; printf(“\nString takes the following path-->\n”); printf(“%d-”,curr1); for(i=0;i { curr1 = go[curr1][str[i]-’0’]; printf(“%d-”,curr1); } printf(“\nFinal state - %d\n”,curr1); for(i=0;i { if(curr1 & (1< { flag = 1; break; }} if(flag) printf(“\nString Accepted”); else printf(“\nString Rejected”); } return 0; } OUTPUT:- NDFA to DFA: EXPERIMENT NO.10 AIM: Design a program to create a PDA machine that accept a well formed parenthesis SOURCE CODE: #include #include #define bool int struct sNode { char data; struct sNode *next; }; void push(struct sNode** top_ref, int new_data); int pop(struct sNode** top_ref); bool isMatchingPair(char character1, char character2) { if (character1 == '(' && character2 == ')') return 1; else if (character1 == '{' && character2 == '}') return 1; else if (character1 == '[' && character2 == ']') return 1; else return 0; } bool areParenthesisBalanced(char exp[]) { int i = 0; struct sNode *stack = NULL; while (exp[i]) { if (exp[i] == '{' || exp[i] == '(' || exp[i] == '[') push(&stack, exp[i]); if (exp[i] == '}' || exp[i] == ')' || exp[i] == ']') { if (stack == NULL) return 0; else if ( !isMatchingPair(pop(&stack), exp[i]) ) return 0; } i++; } if (stack == NULL) return 1; else return 0; } int main() { char exp[100]; printf("\n enter :"); scanf("%s",exp); if (areParenthesisBalanced(exp)) printf("Balanced \n"); else printf("Not Balanced \n"); return 0; } void push(struct sNode** top_ref, int new_data) { struct sNode* new_node = (struct sNode*) malloc(sizeof(struct sNode)); if (new_node == NULL) { printf("Stack overflow n"); getchar(); exit(0); } new_node->data = new_data; new_node->next = (*top_ref); (*top_ref) = new_node; } int pop(struct sNode** top_ref) { char res; struct sNode *top; if (*top_ref == NULL) { printf("Stack overflow n"); getchar(); exit(0); } else { top = *top_ref; res = top->data; *top_ref = top->next; free(top); return res; } } OUTPUT: EXPERIMENT NO.11 AIM: Design a PDA to accept wcwr where w is any string and wr is reverse of that string and C is a special symbol ALGORITHM: Some string will come followed by one 'c', followed by reverse of the string before 'c'. So we get to know that 'c' will work as an alarm to starting poping STACK. So we will pop every 'a' with 'a' and every 'b' with 'b'. For every two a's and b's push them into STACK When 'c' comes do nothing. Starting poping STACK: 'a' for 'a' and 'b' for 'b'. OUTPUT: Designed PDA: Download 1.49 Mb. Share with your friends:
|
1 2