Input/Output

INPUT : baba

OUTPUT: NOT ACCEPTED

INPUT: aaab

OUTPUT: ACCEPTED

Constructing the DFA of the given problem directly is very complicated. So, here we are going to design the non-deterministic finite automata (NFA) and then convert it to the deterministic finite automata (DFA). The NFA of the language containing all the strings in which 2nd symbol from the RHS is “a” is:

Here, A is the initial state and C is the final state. Now, we are going to construct the state transition table of the above NFA.

After that we will draw the state transition table of DFA using subset configuration on the state transition table of NFA. We will mention all the possible transition for a and b.

Now it’s become very easy to draw the DFA with the help of its transition table. In this DFA, we have four different states A, AB, ABC and AC, where ABC and AC are the final states and A is the initial state of the DFA.

This is our required DFA of the language containing the set of all strings over {a, b} in which 2nd symbol from RHS is ‘a’.

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