Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

🔍 Simple Java DFA for validating string patterns like Roman numerals and numeric constants.

NotificationsYou must be signed in to change notification settings

dejesusbg/dfautomaton

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

6 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Overview

A simple Java implementation of a Deterministic Finite Automaton (DFA). This project provides a basic framework to define and run DFAs to recognize specific string patterns based on a given alphabet and a set of state transitions.

The repository includes examples for validating Roman numerals and numeric constants.

Core Components

  • automaton.DFAutomaton: The main class that simulates the DFA. It validates input strings against the defined states and transitions.
  • automaton.State: Represents a single state within the automaton, containing its transitions and whether it is a final (accepting) state.

Getting Started

1. Define Your Alphabet and States

An automaton is defined by an alphabet and an array of states.

  • Alphabet: AString[]. Each string in the array groups characters that trigger the same transition. For example,{"0123456789", ".", "E"}. The index of each string corresponds to a transition path.
  • States: AState[]. EachState object is initialized with:
    • Anint[] for transitions. The index of this array corresponds to the index of the symbol in the alphabet. The value at that index is the index of the next state in thestates array. Use-1 for invalid transitions (trap state).
    • Aboolean indicating if the state is an accepting (valid) final state.

2. Create aDFAutomaton Instance

Instantiate theDFAutomaton class with your alphabet and states array.

DFAutomatonmyAutomaton =newDFAutomaton(myAlphabet,myStates);

3. Test a String

Use theisAccepted(String entry) method to check if a string is recognized by the automaton. It returnstrue if the string ends in a valid state andfalse otherwise.

booleanresult =myAutomaton.isAccepted("your-test-string");

Examples

Thesrc/test/DFA.java file contains complete, runnable examples.

Example 1: Roman Numeral Validator

This DFA validates a simplified set of Roman numerals.

Transition table

// Define the alphabet for Roman numeralsString[]romanAlphabet = {"I","V","X","L","C","D","M"};// Define the state transition tableState[]romanStates = {newState(newint[]{1,2,3,4,5,6,7},false),newState(newint[]{8,9,9, -1, -1, -1, -1},true),newState(newint[]{1, -1, -1, -1, -1, -1, -1},true),newState(newint[]{1,2,10,11,11, -1, -1},true),newState(newint[]{1,2,3, -1, -1, -1, -1},true),newState(newint[]{1,2,3,4,12,13,13},true),newState(newint[]{1,2,3,4,5, -1, -1},true),newState(newint[]{1,2,3,4,5,6,14},true),newState(newint[]{9, -1, -1, -1, -1, -1, -1},true),newState(newint[]{-1, -1, -1, -1, -1, -1, -1},true),newState(newint[]{1,2,11, -1, -1, -1, -1},true),newState(newint[]{1,2, -1, -1, -1, -1, -1},true),newState(newint[]{1,2,3,4,13, -1, -1},true),newState(newint[]{1,2,3,4, -1, -1, -1},true),newState(newint[]{1,2,3,4,5,6,15},true),newState(newint[]{1,2,3,4,5,6, -1},false)};// Create and test the automatonDFAutomatonroman =newDFAutomaton(romanAlphabet,romanStates);System.out.println("Is 'XVI' a valid roman number?: " +roman.isAccepted("XVI"));// trueSystem.out.println("Is 'IIII' a valid roman number?: " +roman.isAccepted("IIII"));// false

Example 2: Numeric Constant Validator

This DFA validates numeric constants, including integers, decimals, and scientific notation (e.g.,1.5E-2).

// Define the alphabet for numeric constantsString[]numAlphabet = {"1234567890",".","E","+-"};// Define the state transition tableState[]numStates = {newState(newint[]{2,7, -1,1},false),newState(newint[]{2,7, -1, -1},false),newState(newint[]{2,3,4, -1},true),newState(newint[]{3, -1,4, -1},true),newState(newint[]{6, -1, -1,5},false),newState(newint[]{6, -1, -1, -1},false),newState(newint[]{6, -1, -1, -1},true),newState(newint[]{3, -1, -1, -1},false)};// Create and test the automatonDFAutomatonnumeric =newDFAutomaton(numAlphabet,numStates);System.out.println("Is '.E2' a valid numeric constant?: " +numeric.isAccepted(".E2"));// trueSystem.out.println("Is '1.5E-2' a valid numeric constant?: " +numeric.isAccepted("1.5E-2"));// trueSystem.out.println("Is '1.E' a valid numeric constant?: " +numeric.isAccepted("1.E"));// false

How to Run

The project is a standard Java project (originally configured for NetBeans). You can compile the source files and run thetest.DFA class from the command line.

  1. Navigate to thesrc directory:

    cd src

  2. Compile the Java files:

    javac automaton/*.java test/*.java

  3. Run the main test class:

    java test.DFA

You should see the following output:

Is a valid roman number?: trueIs a valid numeric constant?: true

About

🔍 Simple Java DFA for validating string patterns like Roman numerals and numeric constants.

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

[8]ページ先頭
©2009-2025 Movatter.jp