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
// C code to implement the above approach
#include <stdio.h>
#include <string.h>
// Driver code
int main()
{
// Input string
char str[20] = { 'c', 'a', 'b', 'c' };
int q = 0, prev_q;
for (int i = 0; i < strlen(str); i++) {
// To check if the string is
// valid or not
if (str[i] != 'a' && str[i] != 'b'
&& str[i] != 'c') {
printf("Given string is invalid.\n");
return 0;
}
// Store the previous state before
// updating it
prev_q = q;
// Update the state based on the
// transition function
switch (q) {
// At state q0, if character
// is 'a' then move to q1
case 0:
q = (str[i] == 'a') ? 1 : 0;
break;
// At state q1, if character
// is 'b' then move to q2 else
// if the character is 'a' then
// remain in same state else
// move to q0
case 1:
q = (str[i] == 'b') ? 2
: (str[i] == 'a') ? 1 : 0;
break;
// At state q2, if character
// is 'c' then move to q3 else
// if the character is 'a' then
// move to q1 state else
// move to q0
case 2:
q = (str[i] == 'c') ? 3
: (str[i] == 'a') ? 1 : 0;
break;
// At state q3, if character
// is 'a' then move to q1 else
// move to q0
case 3:
q = (str[i] == 'a') ? 1 : 0;
break;
}
}
// Check if the dfa machine reached
// the final state
if (q == 3)
printf("ACCEPTED\n");
else
printf("NOT ACCEPTED\n");
return 0;
}
C++
#include <iostream>
#include <cstring>
using namespace std;
// Driver code
int main()
{
// Input string
char str[20] = { 'c', 'a', 'b', 'c' };
int q = 0, prev_q;
for (int i = 0; i < strlen(str); i++) {
// To check if the string is
// valid or not
if (str[i] != 'a' && str[i] != 'b'
&& str[i] != 'c') {
cout << "Given string is invalid.\n";
return 0;
}
// Store the previous state before
// updating it
prev_q = q;
// Update the state based on the
// transition function
switch (q) {
// At state q0, if character
// is 'a' then move to q1
case 0:
q = (str[i] == 'a') ? 1 : 0;
break;
// At state q1, if character
// is 'b' then move to q2 else
// if the character is 'a' then
// remain in same state else
// move to q0
case 1:
q = (str[i] == 'b') ? 2
: (str[i] == 'a') ? 1 : 0;
break;
// At state q2, if character
// is 'c' then move to q3 else
// if the character is 'a' then
// move to q1 state else
// move to q0
case 2:
q = (str[i] == 'c') ? 3
: (str[i] == 'a') ? 1 : 0;
break;
// At state q3, if character
// is 'a' then move to q1 else
// move to q0
case 3:
q = (str[i] == 'a') ? 1 : 0;
break;
}
}
// Check if the dfa machine reached
// the final state
if (q == 3)
cout << "ACCEPTED\n";
else
cout << "NOT ACCEPTED\n";
return 0;
}
Java
// Java program to implement a DFA that accepts
// the language of all strings containing 'a',
// 'b' and 'c' in order.
import java.util.Scanner;
public class GFG {
public static void main(String[] args)
{
// Input string
String str = "cabc";
// Initializing states
int q = 0;
int prev_q;
for (int i = 0; i < str.length(); i++) {
// To check if the string is valid or not
if (str.charAt(i) != 'a' && str.charAt(i) != 'b'
&& str.charAt(i) != 'c') {
System.out.println(
"Given string is invalid.");
return;
}
// Store the previous state before updating it
prev_q = q;
// Update the state based on the transition
// function
switch (q) {
// At state q0, if character is 'a' then move to
// q1
case 0:
q = (str.charAt(i) == 'a') ? 1 : 0;
break;
// At state q1, if character is 'b' then move to
// q2 else if the character is 'a' then remain
// in same state else move to q0
case 1:
q = (str.charAt(i) == 'b')
? 2
: (str.charAt(i) == 'a') ? 1 : 0;
break;
// At state q2, if character is 'c' then move to
// q3 else if the character is 'a' then move to
// q1 state else move to q0
case 2:
q = (str.charAt(i) == 'c')
? 3
: (str.charAt(i) == 'a') ? 1 : 0;
break;
// At state q3, if character is 'a' then move to
// q1 else move to q0
case 3:
q = (str.charAt(i) == 'a') ? 1 : 0;
break;
}
}
// Check if the DFA machine reached the final state
if (q == 3)
System.out.println("ACCEPTED");
else
System.out.println("NOT ACCEPTED");
}
}
Python3
# Python program to implement a DFA that accepts
# the language of all strings containing 'a',
# 'b' and 'c' in order.
# Input string
str = 'cabc'
# Initial state (q0)
q = 0
for i in range(len(str)):
# To check if the string is
# valid or not
if str[i] not in ['a', 'b', 'c']:
print("Given string is invalid.")
exit()
# Store the previous state before
# updating it
prev_q = q
# Update the state based on the
# transition function
if q == 0:
q = 1 if str[i] == 'a' else 0
elif q == 1:
q = 2 if str[i] == 'b' else (1 if str[i] == 'a' else 0)
elif q == 2:
q = 3 if str[i] == 'c' else (1 if str[i] == 'a' else 0)
elif q == 3:
q = 1 if str[i] == 'a' else 0
# Check if the DFA machine reached
# the final state
if q == 3:
print("ACCEPTED")
else:
print("NOT ACCEPTED")
C#
// C# program to implement a DFA that accepts
// the language of all strings containing 'a',
// 'b' and 'c' in order.
using System;
class GFG
{
static void Main()
{
// Input string
char[] str = {'c', 'a', 'b', 'c'};
int q = 0, prev_q;
for (int i = 0; i < str.Length; i++)
{
// To check if the string is valid or not
if (str[i] != 'a' && str[i] != 'b' && str[i] != 'c')
{
Console.WriteLine("Given string is invalid.");
return;
}
// Store the previous state before updating it
prev_q = q;
// Update the state based on the transition function
switch (q)
{
// At state q0, if character is 'a' then move to q1
case 0:
q = (str[i] == 'a') ? 1 : 0;
break;
// At state q1, if character is 'b' then move to q2 else
// if the character is 'a' then remain in same state else
// move to q0
case 1:
q = (str[i] == 'b') ? 2 : (str[i] == 'a') ? 1 : 0;
break;
// At state q2, if character is 'c' then move to q3 else
// if the character is 'a' then move to q1 state else
// move to q0
case 2:
q = (str[i] == 'c') ? 3 : (str[i] == 'a') ? 1 : 0;
break;
// At state q3, if character is 'a' then move to q1 else
// move to q0
case 3:
q = (str[i] == 'a') ? 1 : 0;
break;
}
}
// Check if the dfa machine reached the final state
if (q == 3)
Console.WriteLine("ACCEPTED");
else
Console.WriteLine("NOT ACCEPTED");
}
}
Javascript
<script>
// JavaScript program to implement a DFA that accepts
// the language of all strings containing 'a',
// 'b' and 'c' in order.
let str = "cabc"; // Input string
let q = 0; // Initializing state
let prev_q;
for (let i = 0; i < str.length; i++) {
// To check if the string is valid or not
if (str[i] !== 'a' && str[i] !== 'b' && str[i] !== 'c') {
document.write("Given string is invalid.");
break;
}
// Store the previous state before updating it
prev_q = q;
// Update the state based on the transition function
switch (q) {
// At state q0, if character is 'a' then move to q1
case 0:
q = (str[i] === 'a') ? 1 : 0;
break;
// At state q1, if character is 'b' then move to q2
// else if the character is 'a' then remain in same
// state else move to q0
case 1:
q = (str[i] === 'b') ? 2 : (str[i] === 'a') ? 1 : 0;
break;
// At state q2, if character is 'c' then move to q3
// else if the character is 'a' then move to q1 state
// else move to q0
case 2:
q = (str[i] === 'c') ? 3 : (str[i] === 'a') ? 1 : 0;
break;
// At state q3, if character is 'a' then move to q1
// else move to q0
case 3:
q = (str[i] === 'a') ? 1 : 0;
break;
}
}
// Check if the DFA machine reached the final state
if (q === 3) {
document.write("ACCEPTED");
} else {
document.write("NOT ACCEPTED");
}
// This code is contributed by sankar.
</script>
Output
ACCEPTED
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
