Please program using C (specifically c99) Create a struct DFA, struct NFA, and a
ID: 3881505 • Letter: P
Question
Please program using C (specifically c99) Create a struct DFA, struct NFA, and a struct transition. Please include comments!
1. Implement deterministic finite automata that recognize the following languages:
(a) Exactly the string ab
(b) Any string that starts with the characters ab
(c) Binary input with an even number of 1’s
(d) Binary input with an even number of both 0’s and 1’s
(e) Starts with uni-
For all automata, you may assume that the input alphabet contains exactly the char values greater than 0 and less than 128. This range is the ASCII characters, including upper- and lowercase letters, numbers, and common punctuation. If you want to do something else, document your choice.
2. Implement non-deterministic finite automata that recognize the following languages:
(a) Strings ending in man
(b) Strings with more than one a, g, h, i, o, s, t, or w, or more than two n’s. This automaton is described in FOCS as part of a project to find words that can be made from the letters of the word “Washington” (so-called “partial anagrams”). In this automaton, acceptance means that the input string is not a partial anagram of washington, because it has too many of some letter.
(c) ends in -atic
3. Implement a translator function that receives as input an instance of an NFA and produces as output a (new) instance of a DFA that is equivalent to the original NFA (accepts the same language). Your code should demonstrate the equivalence by running the original NFA and its translation on the three languages you used in Question 2 (the two given in the problem and the one you made up yourself). That is, you will have three functions that produce NFAs from Part 2 of the project. Pass the output of those functions to your converter and run the resulting DFA on user input as described previously.
Explanation / Answer
//1)
#include<stdio.h>
//d even number of 1's and 0's
void Even_10_FA(char s[])
{
int i,c=0;//to count 1's
int d=0;//to count 0's
for(i=0;s[i]!='';i++)
{
if(s[i]=='1')c++;
if(s[i]=='0')d++;
}
//printing output
if(c%2==0 && d%2==0)
printf("Accepted ");
else
printf("Rejected ");
}
//c even number of 1's
void Even_1_FA(char s[])
{
int i,c=0;//to count 1's
for(i=0;s[i]!='';i++)
{
if(s[i]=='1')c++;
}
//printing output
if(c%2==0)
printf("Accepted ");
else
printf("Rejected ");
}
//b start with chars ab
void Start_ab_FA(char s[])
{
int i;
for(i=0;s[i]!='';i++)
{
if(i==0)
{
if(s[i]!='a')break; //check first char
}
else if(i==1)
{
if(s[i]!='b')break; //check second char
}
else
{
break;
}
}
//printing output
if(i==2)
printf("Accepted ");
else
printf("Rejected ");
}
//a Exactly the string ab
void Exact_ab_FA(char s[])
{
int i;
for(i=0;s[i]!='';i++)
{
if(i==0)
{
if(s[i]!='a')break; //check first char
}
else if(i==1)
{
if(s[i]!='b')break; //check second char
}
else
{
i=i+1;
break;
}
}
//printing output
if(i==2)
printf("Accepted ");
else
printf("Rejected ");
}
int main()
{
char stra[100],strb[100],strc[100],strd[100];//max 100 chars
//testing fa's
printf("a:Enter string:");
scanf("%s",stra);
Exact_ab_FA(stra);
printf("b:Enter string:");
scanf("%s",strb);
Start_ab_FA(strb);
printf("c:Enter string:");
scanf("%s",strc);
Even_1_FA(strc);
printf("d:Enter string:");
scanf("%s",strd);
Even_10_FA(strd);
return 0;
}
/*
output:
a:Enter string:ab
Accepted
b:Enter string:abcd
Accepted
c:Enter string:1010
Accepted
d:Enter string:101000
Accepted
Process exited normally.
Press any key to continue . . .
a:Enter string:sc
Rejected
b:Enter string:be
Rejected
c:Enter string:101
Accepted
d:Enter string:10101
Rejected
Process exited normally.
Press any key to continue . . .
a:Enter string:abab
Rejected
b:Enter string:abcd
Accepted
c:Enter string:10101
Rejected
d:Enter string:1010101
Rejected
Process exited normally.
Press any key to continue . . .
*/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.