Theory of Automata and Formal

Download 1.49 Mb.
 Page 1/2 Date 04.09.2021 Size 1.49 Mb.
1   2

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
 S.No. Experiments Page No. Date Remarks 1. Design a Program for creating machine that accepts three consecutive one. 2-3 2. Design a Program for creating machine that accepts the string always ending with 101. 4-5 3. Design a program for Mode 3 machine. 6-7 4. Design a program for Mode 3 machine 8-9 5. Design a program for creating a machine which accepts string having equal number of 1’s and 0’s. 10 6. Design a program for creating a machine which counts number of 1’s and 0’s in given string. 11 7. Design a program to find two’s complement of a given binary number. 12-13 8. Design a program which will increment a given number by one. 14 9. Design a program to convert NDFA to DFA. 15-19 10. Design a program to create a PDA machine that accept a well formed parenthesis 20-22 11. Design a PDA to accept wcwr where w is any string and wr is reverse of that string and C is a special symbol 23 12. Design a Turing Machine that’s accepts the following language L={a^nb^nc^n| where n>1} 24-25 13. Introduction, Setup and installation of JFLAP software. 26 14. Create NFA to DFA using JFLAP software for theory of automata and formal languages 27-28 15. Convert Regular Expression into NFA using JFLAP software for theory of automata and formal languages. 29

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

The database is protected by copyright ©ininet.org 2020
send message

Main page