Horje
Program to construct a DFA to check if a given integer is unsigned or not

Given a string S that represents an integer, the task is to check if the given string S represents an unsigned integer or not by constructing the DFA. If the given string represents an unsigned integer, then print “Unsigned integer”. Otherwise, print “Not an unsigned integer”.

Examples:

Input: S = “+4554”
Output: Not an unsigned integer

Input: S = “1729”
Output: unsigned integer

Approach: Below is the transition states of DFA for the given problem:

Follow the steps below to solve the problem:

  • Declare a function to build and connect DFA states as per the given conditions. Below are the representation of the transitions states:
    • 0 represents a digit.
    • 1 represents sign “+/-“.
    • 2 represents “.” or dot.
    • 3 represents any other character.
    • 4 represents exponent(e/E sign).
  • Initialize a variable, say currentState as 0, that stores the current state in the DFA.
  • Traverse the string S and based on the current state and present character at the current index decide the next state of the DFA.
  • After completing the above steps, if the value of currentState is either 1 or 4 or 8, then print “Unsigned integer”. Otherwise, print “Not an unsigned integer”.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include "bits/stdc++.h"
using namespace std;
 
string digits = "0123456789", sign = "+-";
string dot = ".", ex = "eE";
int dfa[11][5];
 
// Function to construct DFA as per the
// given conditions
void makeDFA()
{
    // If at state 0 and a digit has
    // occurred then set it to state 1
    dfa[0][0] = 1;
 
    // Similarly for all other states
    dfa[1][0] = 1;
    dfa[1][2] = 3;
    dfa[1][3] = 2;
    dfa[1][4] = 6;
 
    dfa[3][0] = 4;
 
    dfa[4][0] = 4;
    dfa[4][3] = 5;
    dfa[4][4] = 6;
 
    dfa[6][0] = 8;
    dfa[6][1] = 7;
 
    dfa[7][0] = 8;
 
    dfa[8][0] = 8;
    dfa[8][3] = 9;
}
 
// Function to build and connect
// the DFA states
void buildDFA()
{
    // Connect all the states to the
    // dead state
    for (int i = 0; i < 11; i++)
        for (int j = 0; j < 5; j++)
            dfa[i][j] = 10;
 
    // Function call to make DFA as
    // per the given conditions
    makeDFA();
}
 
// Function call to check whether an
// integer in the form of string is
// unsigned integer or not
void checkDFA(string s)
{
    // Build the DFA
    buildDFA();
 
    // Stores the current state
    int currentstate = 0;
 
    // Traverse the string
    for (int i = 0; i < s.size(); i++) {
 
        if (digits.find(s[i])
            != digits.npos)
 
            // If at a certain state a
            // digit occurs then change
            // the current state according
            // to the DFA
            currentstate
                = dfa[currentstate][0];
 
        // Or +/- sign
        else if (sign.find(s[i])
                 != sign.npos)
            currentstate
                = dfa[currentstate][1];
 
        // Or decimal occurred
        else if (dot.find(s[i])
                 != dot.npos)
            currentstate
                = dfa[currentstate][2];
 
        // Or any other character
        else if (ex.find(s[i])
                 != ex.npos)
            currentstate
                = dfa[currentstate][4];
 
        // Or e/E or exponent sign
        else
            currentstate
                = dfa[currentstate][3];
    }
 
    // State 1, 4, 8 will give
    // the final answer
    if (currentstate == 1
        || currentstate == 4
        || currentstate == 8) {
        cout << "Unsigned integer";
    }
    else {
        cout << "Not an unsigned integer";
    }
}
 
// Driver Code
int main()
{
    string S = "1729";
    checkDFA(S);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG{
 
static String digits = "0123456789", sign = "+-";
static String dot = ".", ex = "eE";
static int dfa[][] = new int[11][5];
 
// Function to construct DFA as per the
// given conditions
static void makeDFA()
{
     
    // If at state 0 and a digit has
    // occurred then set it to state 1
    dfa[0][0] = 1;
 
    // Similarly for all other states
    dfa[1][0] = 1;
    dfa[1][2] = 3;
    dfa[1][3] = 2;
    dfa[1][4] = 6;
 
    dfa[3][0] = 4;
 
    dfa[4][0] = 4;
    dfa[4][3] = 5;
    dfa[4][4] = 6;
 
    dfa[6][0] = 8;
    dfa[6][1] = 7;
 
    dfa[7][0] = 8;
 
    dfa[8][0] = 8;
    dfa[8][3] = 9;
}
 
// Function to build and connect
// the DFA states
static void buildDFA()
{
     
    // Connect all the states to the
    // dead state
    for(int i = 0; i < 11; i++)
        for(int j = 0; j < 5; j++)
            dfa[i][j] = 10;
 
    // Function call to make DFA as
    // per the given conditions
    makeDFA();
}
 
// Function call to check whether an
// integer in the form of string is
// unsigned integer or not
static void checkDFA(String s)
{
     
    // Build the DFA
    buildDFA();
 
    // Stores the current state
    int currentstate = 0;
 
    // Traverse the string
    for(int i = 0; i < s.length(); i++)
    {
        if (digits.indexOf(s.charAt(i)) != -1)
 
            // If at a certain state a
            // digit occurs then change
            // the current state according
            // to the DFA
            currentstate = dfa[currentstate][0];
 
        // Or +/- sign
        else if (sign.indexOf(s.charAt(i)) != -1)
            currentstate = dfa[currentstate][1];
 
        // Or decimal occurred
        else if (dot.indexOf(s.charAt(i)) != -1)
            currentstate = dfa[currentstate][2];
 
        // Or any other character
        else if (ex.indexOf(s.charAt(i)) != -1)
            currentstate = dfa[currentstate][4];
 
        // Or e/E or exponent sign
        else
            currentstate = dfa[currentstate][3];
    }
 
    // State 1, 4, 8 will give
    // the final answer
    if (currentstate == 1 || currentstate == 4 ||
        currentstate == 8)
    {
        System.out.println("Unsigned integer");
    }
    else
    {
        System.out.println("Not an unsigned integer");
    }
}
 
// Driver Code
public static void main(String[] args)
{
    String S = "1729";
     
    checkDFA(S);
}
}
 
// This code is contributed by Kingash

Python3

# Python3 program for the above approach
digits,sign = "0123456789", "+-"
dot, ex = ".", "eE"
dfa = [[0 for i in range(5)] for i in range(11)]
 
# Function to construct DFA as per the
# given conditions
def makeDFA():
    global dfa
 
    # If at state 0 and a digit has
    # occurred then set it to state 1
    dfa[0][0] = 1
 
    # Similarly for all other states
    dfa[1][0] = 1
    dfa[1][2] = 3
    dfa[1][3] = 2
    dfa[1][4] = 6
 
    dfa[3][0] = 4
 
    dfa[4][0] = 4
    dfa[4][3] = 5
    dfa[4][4] = 6
 
    dfa[6][0] = 8
    dfa[6][1] = 7
 
    dfa[7][0] = 8
 
    dfa[8][0] = 8
    dfa[8][3] = 9
 
 
# Function to build and connect
# the DFA states
def buildDFA():
    global dfa
    # Connect all the states to the
    # dead state
    for i in range(11):
        for j in range(5):
            dfa[i][j] = 10
 
    # Function call to make DFA as
    # per the given conditions
    makeDFA()
 
# Function call to check whether an
# integer in the form of is
# unsigned integer or not
def checkDFA(s):
    # Build the DFA
    buildDFA()
 
    # Stores the current state
    currentstate = 0
 
    # Traverse the string
    for i in range(len(s)):
 
        if (s[i] in digits):
 
            # If at a certain state a
            # digit occurs then change
            # the current state according
            # to the DFA
            currentstate = dfa[currentstate][0]
 
        # Or +/- sign
        elif (s[i] in sign):
            currentstate = dfa[currentstate][1]
 
        # Or decimal occurred
        elif (s[i] in dot):
            currentstate = dfa[currentstate][2]
 
        # Or any other character
        elif (s[i] in ex):
            currentstate = dfa[currentstate][4]
 
        # Or e/E or exponent sign
        else:
            currentstate = dfa[currentstate][3]
 
    # State 1, 4, 8 will give
    # the final answer
    if (currentstate == 1 or currentstate == 4 or currentstate == 8):
        print("Unsigned integer")
    else:
        print("Not an unsigned integer")
 
# Driver Code
if __name__ == '__main__':
    S = "1729"
    checkDFA(S)
 
    # This code is contributed by mohit kumar 29.

C#

// C# program for the above approach
using System;
 
class GFG{
 
static string digits = "0123456789", sign = "+-";
static string dot = ".", ex = "eE";
static int[,] dfa = new int[11, 5];
 
// Function to construct DFA as per the
// given conditions
static void makeDFA()
{
 
    // If at state 0 and a digit has
    // occurred then set it to state 1
    dfa[0, 0] = 1;
 
    // Similarly for all other states
    dfa[1, 0] = 1;
    dfa[1, 2] = 3;
    dfa[1, 3] = 2;
    dfa[1, 4] = 6;
 
    dfa[3, 0] = 4;
 
    dfa[4, 0] = 4;
    dfa[4, 3] = 5;
    dfa[4, 4] = 6;
 
    dfa[6, 0] = 8;
    dfa[6, 1] = 7;
 
    dfa[7, 0] = 8;
 
    dfa[8, 0] = 8;
    dfa[8, 3] = 9;
}
 
// Function to build and connect
// the DFA states
static void buildDFA()
{
 
    // Connect all the states to the
    // dead state
    for(int i = 0; i < 11; i++)
        for(int j = 0; j < 5; j++)
            dfa[i, j] = 10;
 
    // Function call to make DFA as
    // per the given conditions
    makeDFA();
}
 
// Function call to check whether an
// integer in the form of string is
// unsigned integer or not
static void checkDFA(string s)
{
 
    // Build the DFA
    buildDFA();
 
    // Stores the current state
    int currentstate = 0;
 
    // Traverse the string
    for(int i = 0; i < s.Length; i++)
    {
        if (digits.IndexOf(s[i]) != -1)
 
            // If at a certain state a
            // digit occurs then change
            // the current state according
            // to the DFA
            currentstate = dfa[currentstate, 0];
 
        // Or +/- sign
        else if (sign.IndexOf(s[i]) != -1)
            currentstate = dfa[currentstate, 1];
 
        // Or decimal occurred
        else if (dot.IndexOf(s[i]) != -1)
            currentstate = dfa[currentstate, 2];
 
        // Or any other character
        else if (ex.IndexOf(s[i]) != -1)
            currentstate = dfa[currentstate, 4];
 
        // Or e/E or exponent sign
        else
            currentstate = dfa[currentstate, 3];
    }
 
    // State 1, 4, 8 will give
    // the final answer
    if (currentstate == 1 || currentstate == 4 ||
        currentstate == 8)
    {
        Console.WriteLine("Unsigned integer");
    }
    else
    {
        Console.WriteLine("Not an unsigned integer");
    }
}
 
// Driver Code
public static void Main(string[] args)
{
    string S = "1729";
 
    checkDFA(S);
}
}
 
// This code is contributed by ukasp

Javascript

<script>
 
// JavaScript program for the above approach
 
let digits = "0123456789", sign = "+-";
let dot = ".", ex = "eE";
 
let dfa = new Array(11);
for(let i=0;i<11;i++)
{
    dfa[i]=new Array(5);
     
}
 
// Function to construct DFA as per the
// given conditions
function makeDFA()
{
    // If at state 0 and a digit has
    // occurred then set it to state 1
    dfa[0][0] = 1;
  
    // Similarly for all other states
    dfa[1][0] = 1;
    dfa[1][2] = 3;
    dfa[1][3] = 2;
    dfa[1][4] = 6;
  
    dfa[3][0] = 4;
  
    dfa[4][0] = 4;
    dfa[4][3] = 5;
    dfa[4][4] = 6;
  
    dfa[6][0] = 8;
    dfa[6][1] = 7;
  
    dfa[7][0] = 8;
  
    dfa[8][0] = 8;
    dfa[8][3] = 9;
}
 
// Function to build and connect
// the DFA states
function buildDFA()
{
    // Connect all the states to the
    // dead state
    for(let i = 0; i < 11; i++)
        for(let j = 0; j < 5; j++)
            dfa[i][j] = 10;
  
    // Function call to make DFA as
    // per the given conditions
    makeDFA();
}
 
// Function call to check whether an
// integer in the form of string is
// unsigned integer or not
function  checkDFA(s)
{
    // Build the DFA
    buildDFA();
  
    // Stores the current state
    let currentstate = 0;
  
    // Traverse the string
    for(let i = 0; i < s.length; i++)
    {
        if (digits.indexOf(s[i]) != -1)
  
            // If at a certain state a
            // digit occurs then change
            // the current state according
            // to the DFA
            currentstate = dfa[currentstate][0];
  
        // Or +/- sign
        else if (sign.indexOf(s[i]) != -1)
            currentstate = dfa[currentstate][1];
  
        // Or decimal occurred
        else if (dot.indexOf(s[i]) != -1)
            currentstate = dfa[currentstate][2];
  
        // Or any other character
        else if (ex.indexOf(s[i]) != -1)
            currentstate = dfa[currentstate][4];
  
        // Or e/E or exponent sign
        else
            currentstate = dfa[currentstate][3];
    }
  
    // State 1, 4, 8 will give
    // the final answer
    if (currentstate == 1 || currentstate == 4 ||
        currentstate == 8)
    {
        document.write("Unsigned integer<br>");
    }
    else
    {
        document.write("Not an unsigned integer");
    }
}
// Driver Code
let S = "1729";
      
checkDFA(S);
 
 
// This code is contributed by avanitrachhadiya2155
 
</script>

Output: 

Unsigned integer

 

Time Complexity: O(N)
Auxiliary Space: O(1),  since no extra space has been taken.


 


Reffered: https://www.geeksforgeeks.org

Strings

Related
Convert a Mobile Numeric Keypad sequence to equivalent sentence Convert a Mobile Numeric Keypad sequence to equivalent sentence
Maximize cost of removing all occurrences of substrings &quot;ab&quot; and &quot;ba&quot; Maximize cost of removing all occurrences of substrings &quot;ab&quot; and &quot;ba&quot;
Maximize cost of forming a set of words using given set of characters Maximize cost of forming a set of words using given set of characters
Check if 2 * K + 1 non-empty strings exists whose concatenation forms the given string Check if 2 * K + 1 non-empty strings exists whose concatenation forms the given string
Number of substrings with each character occurring even times Number of substrings with each character occurring even times

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 11



 

Horje