C++ & Python Implementation

C++

#include <iostream>
using namespace std;
 
// Forward declarations of state functions
void stateA(string n);
void stateAB(string n);
void stateABC(string n);
void stateAC(string n);
 
// State function for state A
void stateA(string n) {
    // Check if the input string is empty
    if (n.length() == 0) {
        cout << "string not accepted" << endl;
    } else {
        // Check the first character of the input
        if (n[0] == 'a') {
            stateAB(n.substr(1)); // Call stateAB for remaining substring
        } else if (n[0] == 'b') {
            stateA(n.substr(1)); // Call stateA for remaining substring
        }
    }
}
 
// State function for state AB
void stateAB(string n) {
    // Check if the input string is empty
    if (n.length() == 0) {
        cout << "string not accepted" << endl;
    } else {
        // Check the first character of the input
        if (n[0] == 'a') {
            stateABC(n.substr(1)); // Call stateABC for remaining substring
        } else if (n[0] == 'b') {
            stateAC(n.substr(1)); // Call stateAC for remaining substring
        }
    }
}
 
// State function for state ABC
void stateABC(string n) {
    // Check if the input string is empty
    if (n.length() == 0) {
        cout << "string accepted" << endl;
    } else {
        // Check the first character of the input
        if (n[0] == 'a') {
            stateABC(n.substr(1)); // Call stateABC for remaining substring
        } else if (n[0] == 'b') {
            stateAC(n.substr(1)); // Call stateAC for remaining substring
        }
    }
}
 
// State function for state AC
void stateAC(string n) {
    // Check if the input string is empty
    if (n.length() == 0) {
        cout << "string accepted" << endl;
    } else {
        // Check the first character of the input
        if (n[0] == 'a') {
            stateAB(n.substr(1)); // Call stateAB for remaining substring
        } else if (n[0] == 'b') {
            stateA(n.substr(1)); // Call stateA for remaining substring
        }
    }
}
 
int main() {
    string n;
    cin >> n; // Take input string from user
    stateA(n); // Call stateA to check the input
    return 0;
}
 
// This Code is Contributed by Shivam Tiwari

Java

import java.util.Scanner;
 
public class StateMachine {
 
    // Forward declarations of state functions
    static void stateA(String n) {
        // Check if the input string is empty
        if (n.length() == 0) {
            System.out.println("string not accepted");
        } else {
            // Check the first character of the input
            if (n.charAt(0) == 'a') {
                stateAB(n.substring(1)); // Call stateAB for the remaining substring
            } else if (n.charAt(0) == 'b') {
                stateA(n.substring(1)); // Call stateA for the remaining substring
            }
        }
    }
 
    static void stateAB(String n) {
        // Check if the input string is empty
        if (n.length() == 0) {
            System.out.println("string not accepted");
        } else {
            // Check the first character of the input
            if (n.charAt(0) == 'a') {
                stateABC(n.substring(1)); // Call stateABC for the remaining substring
            } else if (n.charAt(0) == 'b') {
                stateAC(n.substring(1)); // Call stateAC for the remaining substring
            }
        }
    }
 
    static void stateABC(String n) {
        // Check if the input string is empty
        if (n.length() == 0) {
            System.out.println("string accepted");
        } else {
            // Check the first character of the input
            if (n.charAt(0) == 'a') {
                stateABC(n.substring(1)); // Call stateABC for the remaining substring
            } else if (n.charAt(0) == 'b') {
                stateAC(n.substring(1)); // Call stateAC for the remaining substring
            }
        }
    }
 
    static void stateAC(String n) {
        // Check if the input string is empty
        if (n.length() == 0) {
            System.out.println("string accepted");
        } else {
            // Check the first character of the input
            if (n.charAt(0) == 'a') {
                stateAB(n.substring(1)); // Call stateAB for the remaining substring
            } else if (n.charAt(0) == 'b') {
                stateA(n.substring(1)); // Call stateA for the remaining substring
            }
        }
    }
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter the string: ");
        if (scanner.hasNext()) {
            String n = scanner.next(); // Take input string from the user
            stateA(n); // Call stateA to check the input
        } else {
            System.out.println("No input provided.");
        }
        scanner.close();
    }
}
 
// This Code is Contributed by Shivam Tiwari

Python3

def stateA(n):
    #if length found 0 
    #print not accepted
    if (len(n)==0):
        print("string not accepted")
    else:    
         
        #if at index 0 
        #'a' found call 
        #function stateAB 
        if(n[0]=='a'):
            stateAB(n[1:])
             
        #else if 'b' found 
        #call function A.    
        elif (n[0]=='b'):
            stateA(n[1:])
         
def stateAB(n):
    #if length found 0 
    #print not accepted
    if (len(n)==0):
        print("string not accepted")
    else:
         
        #if at index 0 
        #'a' found call 
        #function stateABC
        if(n[0]=='a'):
            stateABC(n[1:])
             
        #else if 'b' found 
        #call function AC.     
        elif (n[0]=='b'):
            stateAC(n[1:]) 
         
def stateABC(n):
    #if length found 0 
    #print accepted
    if (len(n)==0):
        print("string accepted")
    else:
         
        #if at index 0 
        #'a' found call 
        #function stateABC
        if(n[0]=='a'):
            stateABC(n[1:])
             
        #else if 'b' found 
        #call function AC.     
        elif (n[0]=='b'):
            stateAC(n[1:])
         
def stateAC(n):
    #if length found 0 
    #print accepted
    if (len(n)==0):
        print("string accepted")
    else:
        #if at index 0 
        #'a' found call 
        #function stateAB
        if(n[0]=='a'):
            stateAB(n[1:])
             
        #else if 'b' found 
        #call function A.     
        elif (n[0]=='b'):
            stateA(n[1:])        
   
 
#take string input
n=input()
 
#call stateA
#to check the input
stateA(n)

C#

using System;
 
class StateMachine
{
    // Forward declarations of state functions
    static void StateA(string n);
    static void StateAB(string n);
    static void StateABC(string n);
    static void StateAC(string n);
 
    // State function for state A
    static void StateA(string n)
    {
        // Check if the input string is null or empty
        if (string.IsNullOrEmpty(n))
        {
            Console.WriteLine("Invalid input: string not accepted");
            return;
        }
 
        // Check the first character of the input
        if (n[0] == 'a')
        {
            StateAB(n.Substring(1)); // Call StateAB for the remaining substring
        }
        else if (n[0] == 'b')
        {
            StateA(n.Substring(1)); // Call StateA for the remaining substring
        }
    }
 
    // State function for state AB
    static void StateAB(string n)
    {
        // Check if the input string is null or empty
        if (string.IsNullOrEmpty(n))
        {
            Console.WriteLine("Invalid input: string not accepted");
            return;
        }
 
        // Check the first character of the input
        if (n[0] == 'a')
        {
            StateABC(n.Substring(1)); // Call StateABC for the remaining substring
        }
        else if (n[0] == 'b')
        {
            StateAC(n.Substring(1)); // Call StateAC for the remaining substring
        }
    }
 
    // State function for state ABC
    static void StateABC(string n)
    {
        // Check if the input string is null or empty
        if (string.IsNullOrEmpty(n))
        {
            Console.WriteLine("string accepted");
            return;
        }
 
        // Check the first character of the input
        if (n[0] == 'a')
        {
            StateABC(n.Substring(1)); // Call StateABC for the remaining substring
        }
        else if (n[0] == 'b')
        {
            StateAC(n.Substring(1)); // Call StateAC for the remaining substring
        }
    }
 
    // State function for state AC
    static void StateAC(string n)
    {
        // Check if the input string is null or empty
        if (string.IsNullOrEmpty(n))
        {
            Console.WriteLine("string accepted");
            return;
        }
 
        // Check the first character of the input
        if (n[0] == 'a')
        {
            StateAB(n.Substring(1)); // Call StateAB for the remaining substring
        }
        else if (n[0] == 'b')
        {
            StateA(n.Substring(1)); // Call StateA for the remaining substring
        }
    }
 
    static void Main()
    {
        Console.Write("Enter a string: ");
        string n = Console.ReadLine(); // Take input string from the user
        StateA(n); // Call StateA to check the input
    }
}
 
// This Code is Contributed by Shivam Tiwari

Javascript

// Forward declarations of state functions
function stateA(n) {
    // Check if the input string is empty
    if (n.length === 0) {
        console.log("String not accepted");
    } else {
        // Check the first character of the input
        if (n[0] === 'a') {
            stateAB(n.substr(1)); // Call stateAB for remaining substring
        } else if (n[0] === 'b') {
            stateA(n.substr(1)); // Call stateA for remaining substring
        }
    }
}
 
function stateAB(n) {
    // Check if the input string is empty
    if (n.length === 0) {
        console.log("String not accepted");
    } else {
        // Check the first character of the input
        if (n[0] === 'a') {
            stateABC(n.substr(1)); // Call stateABC for remaining substring
        } else if (n[0] === 'b') {
            stateAC(n.substr(1)); // Call stateAC for remaining substring
        }
    }
}
 
function stateABC(n) {
    // Check if the input string is empty
    if (n.length === 0) {
        console.log("String accepted");
    } else {
        // Check the first character of the input
        if (n[0] === 'a') {
            stateABC(n.substr(1)); // Call stateABC for remaining substring
        } else if (n[0] === 'b') {
            stateAC(n.substr(1)); // Call stateAC for remaining substring
        }
    }
}
 
function stateAC(n) {
    // Check if the input string is empty
    if (n.length === 0) {
        console.log("String accepted");
    } else {
        // Check the first character of the input
        if (n[0] === 'a') {
            stateAB(n.substr(1)); // Call stateAB for remaining substring
        } else if (n[0] === 'b') {
            stateA(n.substr(1)); // Call stateA for remaining substring
        }
    }
}
 
// Driver code
let inputString = prompt("Enter a string: "); // Take input string from the user
stateA(inputString); // Call stateA to check the input
//This code is contributed by Monu.

DFA of a string in which 2nd symbol from RHS is ‘a’

Draw deterministic finite automata (DFA) of the language containing the set of all strings over {a, b} in which 2nd symbol from RHS is ‘a’. The strings in which 2nd last symbol is “a” are:

aa, ab, aab, aaa, aabbaa, bbbab etc

Similar Reads

C++ #include using namespace std; // Forward declarations of state functions void stateA(string n); void stateAB(string n); void stateABC(string n); void stateAC(string n); // State function for state A void stateA(string n) { // Check if the input string is empty if (n.length() == 0) { cout << "string not accepted" << endl; } else { // Check the first character of the input if (n[0] == 'a') { stateAB(n.substr(1)); // Call stateAB for remaining substring } else if (n[0] == 'b') { stateA(n.substr(1)); // Call stateA for remaining substring } } } // State function for state AB void stateAB(string n) { // Check if the input string is empty if (n.length() == 0) { cout << "string not accepted" << endl; } else { // Check the first character of the input if (n[0] == 'a') { stateABC(n.substr(1)); // Call stateABC for remaining substring } else if (n[0] == 'b') { stateAC(n.substr(1)); // Call stateAC for remaining substring } } } // State function for state ABC void stateABC(string n) { // Check if the input string is empty if (n.length() == 0) { cout << "string accepted" << endl; } else { // Check the first character of the input if (n[0] == 'a') { stateABC(n.substr(1)); // Call stateABC for remaining substring } else if (n[0] == 'b') { stateAC(n.substr(1)); // Call stateAC for remaining substring } } } // State function for state AC void stateAC(string n) { // Check if the input string is empty if (n.length() == 0) { cout << "string accepted" << endl; } else { // Check the first character of the input if (n[0] == 'a') { stateAB(n.substr(1)); // Call stateAB for remaining substring } else if (n[0] == 'b') { stateA(n.substr(1)); // Call stateA for remaining substring } } } int main() { string n; cin >> n; // Take input string from user stateA(n); // Call stateA to check the input return 0; } // This Code is Contributed by Shivam Tiwari Java import java.util.Scanner; public class StateMachine { // Forward declarations of state functions static void stateA(String n) { // Check if the input string is empty if (n.length() == 0) { System.out.println("string not accepted"); } else { // Check the first character of the input if (n.charAt(0) == 'a') { stateAB(n.substring(1)); // Call stateAB for the remaining substring } else if (n.charAt(0) == 'b') { stateA(n.substring(1)); // Call stateA for the remaining substring } } } static void stateAB(String n) { // Check if the input string is empty if (n.length() == 0) { System.out.println("string not accepted"); } else { // Check the first character of the input if (n.charAt(0) == 'a') { stateABC(n.substring(1)); // Call stateABC for the remaining substring } else if (n.charAt(0) == 'b') { stateAC(n.substring(1)); // Call stateAC for the remaining substring } } } static void stateABC(String n) { // Check if the input string is empty if (n.length() == 0) { System.out.println("string accepted"); } else { // Check the first character of the input if (n.charAt(0) == 'a') { stateABC(n.substring(1)); // Call stateABC for the remaining substring } else if (n.charAt(0) == 'b') { stateAC(n.substring(1)); // Call stateAC for the remaining substring } } } static void stateAC(String n) { // Check if the input string is empty if (n.length() == 0) { System.out.println("string accepted"); } else { // Check the first character of the input if (n.charAt(0) == 'a') { stateAB(n.substring(1)); // Call stateAB for the remaining substring } else if (n.charAt(0) == 'b') { stateA(n.substring(1)); // Call stateA for the remaining substring } } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); System.out.print("Enter the string: "); if (scanner.hasNext()) { String n = scanner.next(); // Take input string from the user stateA(n); // Call stateA to check the input } else { System.out.println("No input provided."); } scanner.close(); } } // This Code is Contributed by Shivam Tiwari Python3 def stateA(n): #if length found 0 #print not accepted if (len(n)==0): print("string not accepted") else: #if at index 0 #'a' found call #function stateAB if(n[0]=='a'): stateAB(n[1:]) #else if 'b' found #call function A. elif (n[0]=='b'): stateA(n[1:]) def stateAB(n): #if length found 0 #print not accepted if (len(n)==0): print("string not accepted") else: #if at index 0 #'a' found call #function stateABC if(n[0]=='a'): stateABC(n[1:]) #else if 'b' found #call function AC. elif (n[0]=='b'): stateAC(n[1:]) def stateABC(n): #if length found 0 #print accepted if (len(n)==0): print("string accepted") else: #if at index 0 #'a' found call #function stateABC if(n[0]=='a'): stateABC(n[1:]) #else if 'b' found #call function AC. elif (n[0]=='b'): stateAC(n[1:]) def stateAC(n): #if length found 0 #print accepted if (len(n)==0): print("string accepted") else: #if at index 0 #'a' found call #function stateAB if(n[0]=='a'): stateAB(n[1:]) #else if 'b' found #call function A. elif (n[0]=='b'): stateA(n[1:]) #take string input n=input() #call stateA #to check the input stateA(n) C# using System; class StateMachine { // Forward declarations of state functions static void StateA(string n); static void StateAB(string n); static void StateABC(string n); static void StateAC(string n); // State function for state A static void StateA(string n) { // Check if the input string is null or empty if (string.IsNullOrEmpty(n)) { Console.WriteLine("Invalid input: string not accepted"); return; } // Check the first character of the input if (n[0] == 'a') { StateAB(n.Substring(1)); // Call StateAB for the remaining substring } else if (n[0] == 'b') { StateA(n.Substring(1)); // Call StateA for the remaining substring } } // State function for state AB static void StateAB(string n) { // Check if the input string is null or empty if (string.IsNullOrEmpty(n)) { Console.WriteLine("Invalid input: string not accepted"); return; } // Check the first character of the input if (n[0] == 'a') { StateABC(n.Substring(1)); // Call StateABC for the remaining substring } else if (n[0] == 'b') { StateAC(n.Substring(1)); // Call StateAC for the remaining substring } } // State function for state ABC static void StateABC(string n) { // Check if the input string is null or empty if (string.IsNullOrEmpty(n)) { Console.WriteLine("string accepted"); return; } // Check the first character of the input if (n[0] == 'a') { StateABC(n.Substring(1)); // Call StateABC for the remaining substring } else if (n[0] == 'b') { StateAC(n.Substring(1)); // Call StateAC for the remaining substring } } // State function for state AC static void StateAC(string n) { // Check if the input string is null or empty if (string.IsNullOrEmpty(n)) { Console.WriteLine("string accepted"); return; } // Check the first character of the input if (n[0] == 'a') { StateAB(n.Substring(1)); // Call StateAB for the remaining substring } else if (n[0] == 'b') { StateA(n.Substring(1)); // Call StateA for the remaining substring } } static void Main() { Console.Write("Enter a string: "); string n = Console.ReadLine(); // Take input string from the user StateA(n); // Call StateA to check the input } } // This Code is Contributed by Shivam Tiwari Javascript // Forward declarations of state functions function stateA(n) { // Check if the input string is empty if (n.length === 0) { console.log("String not accepted"); } else { // Check the first character of the input if (n[0] === 'a') { stateAB(n.substr(1)); // Call stateAB for remaining substring } else if (n[0] === 'b') { stateA(n.substr(1)); // Call stateA for remaining substring } } } function stateAB(n) { // Check if the input string is empty if (n.length === 0) { console.log("String not accepted"); } else { // Check the first character of the input if (n[0] === 'a') { stateABC(n.substr(1)); // Call stateABC for remaining substring } else if (n[0] === 'b') { stateAC(n.substr(1)); // Call stateAC for remaining substring } } } function stateABC(n) { // Check if the input string is empty if (n.length === 0) { console.log("String accepted"); } else { // Check the first character of the input if (n[0] === 'a') { stateABC(n.substr(1)); // Call stateABC for remaining substring } else if (n[0] === 'b') { stateAC(n.substr(1)); // Call stateAC for remaining substring } } } function stateAC(n) { // Check if the input string is empty if (n.length === 0) { console.log("String accepted"); } else { // Check the first character of the input if (n[0] === 'a') { stateAB(n.substr(1)); // Call stateAB for remaining substring } else if (n[0] === 'b') { stateA(n.substr(1)); // Call stateA for remaining substring } } } // Driver code let inputString = prompt("Enter a string: "); // Take input string from the user stateA(inputString); // Call stateA to check the input //This code is contributed by Monu....

Tags:

#GATE CS #Theory of Computation

Transition Table

Output