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