HTTPS SSH

Welcome

Welcome to nfa-simulator wiki!

Nfa-simulator is a non-determinstic finished machine simulator written in c++.

It read the nfa definition from the provided configuration file and test if a provided string bring the machine in a final(or acceptor) state.

The simulator can also start parallel computations in order to follow any possible transition as defined in the input file.

Getting started

Download code The project source code can be downloaded from the download page, under 'download repository', or by cloning this repository

Building on windows: You can build this project by using mingw32-make. Mingw32-make is provided with the TDM Mingw32 compiler (see http://tdm-gcc.tdragon.net/download)

 C:/dir>mingw32-make -f makefile.win

Building on Linux /unix: Building is execute by calling standard unix make

 $>make -f makefile.linux

Usage

nfa_simulator [-v] -i config_file -t test_string

where:

  • -i: Nfa definition input file
  • -t: String to test if is matched by the nfa
  • -v: Optional, verbose, show info of parsing/computation

Input file syntax

The definition file describe the nfa statuses and transitions line by line

Every definition line must be in the format:

qX:sA=LIST;sB=LIST;...;sZ=LIST;final=VAL

Where:

  • qX identify the state number X , with X number starting from 0
  • sA,..,sZ identify the A..Z symbols of the alphabet
  • LIST is the list of states the machine (in the state define at the beginning of the line) will reach by reading the simbol written before the list. This list must be a list of states separated by ',': 'q0,q4,q11' or 'q1' in the case of a single state
  • final is an optional parameter telling that this is a final (or acceptor) state. Possibile values for VAL are: yes,no. If not specified the default value is no (aka the state is not final)

A special line can be used to specify the initial state of the machine:

init-state=qX

If no such string is provided, the machine will start from q0.

If the specified state is not defined by any of the definition lines, the machine will halt.

Example file

init-state=q1
q0:sa=q0,q1;s0=q0
q1:sa=q2;s0=q0,q1
q2:s0=q0;final=yes