Program to build DFA that accepts the languages ending with “01” over the characters {0, 1}
Given a binary string str, the task is to build a DFA that accepts the languages ending with “01” over the characters {0, 1}.
Examples:
Input: str = “00011101” Output: String Accepted Explanation: As the given string ends with “01”, therefore, it is accepted.
Input: str = “00001111” Output: String Rejected Explanation: As the given string ends with “11”, therefore, it is rejected.
Approach: To solve the above problem, below are the class state and member function needed:
- Pair 1: It deals with the first type of input i.e. 0 and links it with an object pointer to the next state.
- Pair 2: It deals with the second type of input i.e. 1 and links it with an object pointer to the next state.
- m_x: It defines whether a particular state is initial or final.
Class member functions are defined below:
- initialize(): This function takes the two pairs(used for two kinds of inputs) as parameters along with the state defining character(i or f).
- transition(): This acts as a transition table for the automata and with a particular input it goes from one state to next state.
- traverse(): This function takes the input string and passes it through the automata.
- check(): This function checks whether after the input has ended the end state is a final state or not. If it is final then the string is accepted otherwise rejected.
For this problem three states are needed. Hence, create three-class objects and initialize them with required values as:
- State 1: On input 0 it goes to State 2 and on input 1 it goes to itself.
- State 2: On input 0 it goes to itself and on input 1 it goes to State 3.
- State 3: On input 0 it goes to State 2 and on input 1 goes to State 1. Also, this is our final state.
Below is the implementation of the above approach:
C++14
// C++ program of a DFA that accepts // all string ending with "01" #include <iostream> #include <string> using namespace std; // Class for automata class State { private : // Data members to store the input pair< int , State*> Pair1; pair< int , State*> Pair2; char m_x; public : // Pointer to the state of automata static State* m_ptr; // Constructor to initialize state State() { Pair1.first = 0; Pair1.second = nullptr; Pair2.first = 0; Pair2.second = nullptr; m_x = ' ' ; } // Initialise pair1 and pair2 // with state x void initialize( pair< int , State*> pair1, pair< int , State*> pair2, char x) { Pair1 = pair1; Pair2 = pair2; m_x = x; } // Passes a string through automata static void transition( int input); static void traverse(string& str, int n); // Checks if the last state // is final or not static void check(); }; // Pointer to the current // state of automata State* State::m_ptr{ nullptr }; // Function to provide state // transition of automata void State::transition( int input) { if ((*m_ptr).Pair1.first == input) m_ptr = (*m_ptr).Pair1.second; else m_ptr = (*m_ptr).Pair2.second; } // Checks if the last state // is final or not void State::check() { if ((*m_ptr).m_x == 'f' ) cout << "String Accepted\n" << endl; else cout << "String Rejected\n" << endl; } // Passes a string through automata void State::traverse(string& str, int n) { for ( int i = 0; i < n; i++) { int x{ ( int )str[i] - ( int ) '0' }; transition(x); } } // Function to check if the given // is accepted in DFA or not void isAccepted(string str) { // States of the automata State one, two, three; // Transition table for required // automata one.initialize({ 0, &two }, { 1, &one }, 'i' ); two.initialize({ 0, &two }, { 1, &three }, 'i' ); three.initialize({ 0, &two }, { 1, &one }, 'f' ); int length{ static_cast < int >(str.length()) }; State::m_ptr = &one; // Function call State::traverse(str, length); State::check(); } // Driver Code int main() { string str{ "00111101" }; isAccepted(str); return 0; } |
Java
public class State { // Data members to store the input private int [] Pair1; private int [] Pair2; private char m_x; // Pointer to the state of automata private static State m_ptr = null ; // Constructor public State() { this .Pair1 = new int []{ 0 , - 1 }; this .Pair2 = new int []{ 0 , - 1 }; this .m_x = ' ' ; } // Initialise pair1 and pair2 with state x public void initialize( int [] pair1, int [] pair2, char x) { this .Pair1 = pair1; this .Pair2 = pair2; this .m_x = x; } // Passes an input through automata public void transition( int input) { if (Pair1[ 0 ] == input) { m_ptr = getState(Pair1[ 1 ]); } else { m_ptr = getState(Pair2[ 1 ]); } } // Helper function to get the state based on the index private static State getState( int index) { switch (index) { case 0 : return new State(); case 1 : return new State(); case 2 : return new State(); default : return new State(); // Return a default state for invalid indexes } } public static void traverse(String str) { int n = str.length(); for ( int i = 0 ; i < n; i++) { int x = Character.getNumericValue(str.charAt(i)); m_ptr.transition(x); } } // Checks if the last state is final or not public void check() { if (m_x == 'f' ) { System.out.println( "String Accepted" ); } else { System.out.println( "String Rejected" ); } } // Function to check if the given string is accepted in DFA or not public static void isAccepted(String str) { // States of the automata State one = new State(); State two = new State(); State three = new State(); // Transition table for the required automata one.initialize( new int []{ 0 , 1 }, new int []{ 1 , 0 }, 'i' ); two.initialize( new int []{ 0 , 1 }, new int []{ 1 , 2 }, 'i' ); three.initialize( new int []{ 0 , 1 }, new int []{ 1 , 0 }, 'f' ); int length = str.length(); m_ptr = one; // Function call traverse(str); m_ptr.check(); } // Driver Code public static void main(String[] args) { String str = "00111101" ; isAccepted(str); } } |
Python3
class State: # Data members to store the input def __init__( self ): self .Pair1 = [ 0 , None ] self .Pair2 = [ 0 , None ] self .m_x = ' ' # Pointer to the state of automata m_ptr = None # Initialise pair1 and pair2 # with state x def initialize( self , pair1, pair2, x): self .Pair1 = pair1 self .Pair2 = pair2 self .m_x = x # Passes a string through automata @staticmethod def transition( input ): if State.m_ptr.Pair1[ 0 ] = = input : State.m_ptr = State.m_ptr.Pair1[ 1 ] else : State.m_ptr = State.m_ptr.Pair2[ 1 ] @staticmethod def traverse( str , n): for i in range (n): x = int ( str [i]) - int ( '0' ) State.transition(x) # Checks if the last state # is final or not @staticmethod def check(): if State.m_ptr.m_x = = 'f' : print ( "String Accepted\n" ) else : print ( "String Rejected\n" ) # Function to check if the given # is accepted in DFA or not def isAccepted( str ): # States of the automata one = State() two = State() three = State() # Transition table for required # automata one.initialize([ 0 , two], [ 1 , one], 'i' ) two.initialize([ 0 , two], [ 1 , three], 'i' ) three.initialize([ 0 , two], [ 1 , one], 'f' ) length = len ( str ) State.m_ptr = one # Function call State.traverse( str , length) State.check() # Driver Code str = "00111101" isAccepted( str ) |
C#
// C# program of a DFA that accepts // all string ending with "01" using System; // Class for automata class State { // Data members to store the input private Tuple< int , State> Pair1; private Tuple< int , State> Pair2; private char m_x; // Pointer to the state of automata public static State m_ptr; // Constructor to initialize state public State() { Pair1 = new Tuple< int , State>(0, null ); Pair2 = new Tuple< int , State>(0, null ); m_x = ' ' ; } // Initialise pair1 and pair2 // with state x public void Initialize(Tuple< int , State> pair1, Tuple< int , State> pair2, char x) { Pair1 = pair1; Pair2 = pair2; m_x = x; } // Function to provide state // transition of automata public static void Transition( int input) { if (m_ptr.Pair1.Item1 == input) { m_ptr = m_ptr.Pair1.Item2; } else { m_ptr = m_ptr.Pair2.Item2; } } // Passes a string through automata public static void Traverse( string str, int n) { for ( int i = 0; i < n; i++) { int x = ( int )Char.GetNumericValue(str[i]); Transition(x); } } // Checks if the last state // is final or not public static void Check() { if (m_ptr.m_x == 'f' ) { Console.WriteLine( "String Accepted\n" ); } else { Console.WriteLine( "String Rejected\n" ); } } } class Program { // Function to check if the given // is accepted in DFA or not static void IsAccepted( string str) { // States of the automata State one = new State(); State two = new State(); State three = new State(); // Transition table for required // automata one.Initialize( new Tuple< int , State>(0, two), new Tuple< int , State>(1, one), 'i' ); two.Initialize( new Tuple< int , State>(0, two), new Tuple< int , State>(1, three), 'i' ); three.Initialize( new Tuple< int , State>(0, two), new Tuple< int , State>(1, one), 'f' ); int length = str.Length; State.m_ptr = one; // Function call State.Traverse(str, length); State.Check(); } // Driver Code static void Main( string [] args) { string str = "00111101" ; IsAccepted(str); } } |
Javascript
class State { // Data members to store the input constructor() { this .Pair1 = [0, null ]; this .Pair2 = [0, null ]; this .m_x = ' ' ; } // Pointer to the state of automata static m_ptr = null ; // Initialise pair1 and pair2 // with state x initialize(pair1, pair2, x) { this .Pair1 = pair1; this .Pair2 = pair2; this .m_x = x; } // Passes a string through automata static transition(input) { if (State.m_ptr.Pair1[0] == input) { State.m_ptr = State.m_ptr.Pair1[1]; } else { State.m_ptr = State.m_ptr.Pair2[1]; } } static traverse(str, n) { for (let i = 0; i < n; i++) { let x = parseInt(str[i]) - parseInt( '0' ); State.transition(x); } } // Checks if the last state // is final or not static check() { if (State.m_ptr.m_x == 'f' ) { console.log( "String Accepted\n" ); } else { console.log( "String Rejected\n" ); } } } // Function to check if the given // is accepted in DFA or not function isAccepted(str) { // States of the automata let one = new State(); let two = new State(); let three = new State(); // Transition table for required // automata one.initialize([0, two], [1, one], 'i' ); two.initialize([0, two], [1, three], 'i' ); three.initialize([0, two], [1, one], 'f' ); let length = str.length; State.m_ptr = one; // Function call State.traverse(str, length); State.check(); } // Driver Code let str = "00111101" ; isAccepted(str); |
Output
String Accepted
Time Complexity: O(N) Auxiliary Space: O(1)
Contact Us