Program to build a DFA that accepts Strings ending with abc

By Ann Roberts On Feb 16, 2023

Given a string, str consists of characters ‘a’, ‘b’ & ‘c’, the task is to check whether string str ends with “abc” or not. If it does, print ‘Accepted’ with state transitions, else print ‘Not Accepted’.

Examples:

Input: str = “cbabc”
Output: Accepted
Explanation: c : q0–>q0
b: q0–>q0
a: q0–>q1
b: q1–>q2
c: q2–>q3
The string “cbabc” is ending with ‘abc’. It is in final state q3. So the string is accepted.

Input: str = “ababa”
Output: Not accepted
Explanation: c: q0–>q0
b: q0–>q0
a: q0–>q1
c: q1–>q0
The string “cbac” is not ending with ‘abc’. It is in the state q0. So the string is not accepted.

DFA Machine: For the above problem statement build a DFA machine. DFA machine corresponding to the above problem is shown below, q0 is the initial state and q3 is the final state.

DFA Machine

Approach: Implement the idea below to solve the problem:

Suppose the first character in the input string is ‘a’, then on reading ‘a’, the control will shift to state q1 from q0, else if the first character is either ‘b’ or ‘c’ then the control remains in same state. At state q0, until we get character ‘a’, it keeps circulating at the same state. At state q1, if the character is ‘b’, then it moves to the state q2 from q1. If character ‘a’ is encountered at state q1, then it remains at the same state. If character ‘c’ is encounters then we move to initial state. At state q2, if the character is ‘c’ then it moves to the final state q3. At state q2, if character ‘a’ comes then it will shift the control to state q1, else it goes to initial state. If the string ends at final state, we return “Accepted”. At final state, if character ‘a’ encounters, then it moves to the state q1 else it shifts its control to the q0 state.

For the given DFA Machine, the specifications are as follows:

q0, q1, q2, q3 are the defined states.
a, b, and c are valid symbols. Each state has a transition defined for a, b, and c.
q3 is the final state. If the input string ends at this state, it is accepted else rejected.
If by following the process, the program reaches the end of the string, the output is made according to the state the program is at.

Steps were taken to solve the problem:

Read the string.
For each character in the string, check if it is ‘a’, ‘b’, or ‘c’. If not, return “Invalid string!! The string is not accepted.”
Keep track of the current state and the previous state.
For each character, update the current state based on the transition diagram.
If the final state is q3, return “Accepted.”
If the final state is not q3, return “Not accepted.”

Below is the implementation of the above approach:

C

#include <stdio.h>

#include <string.h>

int main()

{

char str[20] = { 'c', 'a', 'b', 'c' };

int q = 0, prev_q;

for (int i = 0; i < strlen(str); i++) {

if (str[i] != 'a' && str[i] != 'b'

&& str[i] != 'c') {

printf("Given string is invalid.\n");

return 0;

}

prev_q = q;

switch (q) {

case 0:

q = (str[i] == 'a') ? 1 : 0;

break;

case 1:

q = (str[i] == 'b') ? 2

: (str[i] == 'a') ? 1 : 0;

break;

case 2:

q = (str[i] == 'c') ? 3

: (str[i] == 'a') ? 1 : 0;

break;

case 3:

q = (str[i] == 'a') ? 1 : 0;

break;

}

if (q == 3)

printf("ACCEPTED\n");

else

printf("NOT ACCEPTED\n");

return 0;

}

Time Complexity: O(N)
Auxiliary Space: O(1)

Examples:

Input: str = “cbabc”
Output: Accepted
Explanation: c : q0–>q0
b: q0–>q0
a: q0–>q1
b: q1–>q2
c: q2–>q3
The string “cbabc” is ending with ‘abc’. It is in final state q3. So the string is accepted.

Input: str = “ababa”
Output: Not accepted
Explanation: c: q0–>q0
b: q0–>q0
a: q0–>q1
c: q1–>q0
The string “cbac” is not ending with ‘abc’. It is in the state q0. So the string is not accepted.

DFA Machine: For the above problem statement build a DFA machine. DFA machine corresponding to the above problem is shown below, q0 is the initial state and q3 is the final state.

DFA Machine

Approach: Implement the idea below to solve the problem:

Suppose the first character in the input string is ‘a’, then on reading ‘a’, the control will shift to state q1 from q0, else if the first character is either ‘b’ or ‘c’ then the control remains in same state. At state q0, until we get character ‘a’, it keeps circulating at the same state. At state q1, if the character is ‘b’, then it moves to the state q2 from q1. If character ‘a’ is encountered at state q1, then it remains at the same state. If character ‘c’ is encounters then we move to initial state. At state q2, if the character is ‘c’ then it moves to the final state q3. At state q2, if character ‘a’ comes then it will shift the control to state q1, else it goes to initial state. If the string ends at final state, we return “Accepted”. At final state, if character ‘a’ encounters, then it moves to the state q1 else it shifts its control to the q0 state.

For the given DFA Machine, the specifications are as follows:

q0, q1, q2, q3 are the defined states.
a, b, and c are valid symbols. Each state has a transition defined for a, b, and c.
q3 is the final state. If the input string ends at this state, it is accepted else rejected.
If by following the process, the program reaches the end of the string, the output is made according to the state the program is at.

Steps were taken to solve the problem:

Read the string.
For each character in the string, check if it is ‘a’, ‘b’, or ‘c’. If not, return “Invalid string!! The string is not accepted.”
Keep track of the current state and the previous state.
For each character, update the current state based on the transition diagram.
If the final state is q3, return “Accepted.”
If the final state is not q3, return “Not accepted.”

Below is the implementation of the above approach:

C

#include <stdio.h>

#include <string.h>

int main()

{

char str[20] = { 'c', 'a', 'b', 'c' };

int q = 0, prev_q;

for (int i = 0; i < strlen(str); i++) {

if (str[i] != 'a' && str[i] != 'b'

&& str[i] != 'c') {

printf("Given string is invalid.\n");

return 0;

}

prev_q = q;

switch (q) {

case 0:

q = (str[i] == 'a') ? 1 : 0;

break;

case 1:

q = (str[i] == 'b') ? 2

: (str[i] == 'a') ? 1 : 0;

break;

case 2:

q = (str[i] == 'c') ? 3

: (str[i] == 'a') ? 1 : 0;

break;

case 3:

q = (str[i] == 'a') ? 1 : 0;

break;

}

if (q == 3)

printf("ACCEPTED\n");

else

printf("NOT ACCEPTED\n");

return 0;

}

Time Complexity: O(N)
Auxiliary Space: O(1)

Read original article here

Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.