maggieezzat/automaton-theory

A basic Implementation of a Deterministic Finite State Automaton (DFA), Non-Deterministic Finite State Automaton (NFA) and Fallback DFA with Actions (FDFA) along with the Left Recursion Elimination algorithm for a Context-Free-Grammar (CFG)

DFA

• A basic Implementation of a Deterministic Finite State Automaton (DFA)
• A DFA is a quintuple ( , , , , ):
  • is a non-empty, finite set of states.
  • is non-empty, finite set of symbols (an alphabet).
  • → is the transition function.
  • is the start state.
  • is the set of accept states.
• A DFA accepts a string if there is a sequence of states such that
  • 
  • 
  • (r_i,w_i+1) = r_i+1"> for every

We make the following assumptions for simplicity.

1. The alphabet is always the binary alphabet {0,1}
2. The set of states is always of the form The set of states {0, . . . , n}, for some .
3. The start state is always state 0.

An object DFA is implemented, where:

• DFA is created by calling the function construct_DFA which takes one parameter that is a string description of a DFA and returns a DFA instance.
• A string describing a DFA is of the form P#S, where P is a prefix representing the transition function and S is a suffix representing the set ) of accept state.
• P is a semicolon-separated sequence of triples of states: each triple is a comma-separated sequence of states. A triple i, j, k means that (i,0) = j and (i,1) = k
• S is a comma-separated sequence of states.
• For example, the DFA for which the state diagram appears below may have the following string representation: 0,0,1;1,2,1;2,0,3;3,3,3#1,3

• run simulates the operation of the constructed DFA on a given binary string. It returns true if the string is accepted by the DFA and false otherwise.

NFA

• An implementation of the classical algorithm for constructing a deterministic finite automaton (DFA) equivalent to a non-deterministic finite automaton (NFA).
• A NFA is a quintuple ( , , , , ):
  • is a non-empty, finite set of states.
  • is non-empty, finite set of symbols (an alphabet).
  • → is the transition function.
  • is the start state.
  • is the set of accept states.
• Given a description of an NFA, we will construct an equivalent DFA.
• Same assumptions followed in DFA will hold in NFA

An object DFA is implemented, where:

• DFA is created by calling the function decode_NFA which takes one parameter that is a string description of a NFA and returns a DFA instance.
• A string describing an NFA is of the form Z#O#E#F, where Z, O, and E, respectively, represent the 0-transitions, the 1-transitions, and the -transitions. F represents the set of accept state.
• Z, O, and E are semicolon-separated sequences of pairs of states. Each pair is a comma-separated sequence of two states. A pair i, j represents a transition from state i to state j. For Z this means that (i, 0) = j, similarly for O and E.
• F is a comma-separated sequence of states.
• For example, the NFA for which the state diagram appears below may have the following string representation: 0,0;1,2;3,3#0,0;0,1;2,3;3,3#1,2#3
• run simulates the operation of the constructed DFA on a given binary string. It returns true if the string is accepted by the DFA and false otherwise.

FDFA

• An implementation of a fallback deterministic finite automaton with actions (FDFA) abstract data type.
• A FDFA is a sextuple ( , , , , , ):
  • is a non-empty, finite set of states.
  • is non-empty, finite set of symbols (an alphabet).
  • → is the transition function.
  • is the start state.
  • is the set of accept states.
  • is function that maps every state in Q to an action.
• Same assumptions followed in DFA will hold in FDFA

An object FDFA is implemented, where:

• FDFA is created by calling the function construct_fdfa which takes one parameter that is a string description of a FDFA and returns a FDFA instance.
• A string describing an FDFA is of the form P#S, where P is a prefix representing both the transition function and the action function and S is a suffix representing the set of accept state.
• P is a semicolon-separated sequence of quadruples. Each quadruple is a comma-separated sequence of items: the first three items are states and the fourth is a binary string. A quadruple i, j, k, s means that (i, 0) = j, (i, 1) = k, and (i) = s.
• S is a comma-separated sequence of states.
• For example, consider the FDFA for which the state diagram appears below. Suppose that, for state i, A(i) is the two-bit binary representation of i. Thus, such an FDFA may have the following string representation: 0,0,1,00;1,2,1,01;2,0,3,10;3,3,3,11#0,1,2

• run simulates the operation of the constructed FDFA on a given binary string. For example, running the above FDFA on the string 1011100 produces the output 1000.

CFG Left Recursion Elimination

• An implementation of the Context Free Grammar (CFG) Left Recursion Elimination Algorithm.
• a CFG is a quadruple (, , , ) where:
  • and are disjoint alphabets (respectively, containing variables and terminals).
  • is a set of rules.
  • is the start variable.

We make the following assumptions for simplicity:

1. The set of variables consists of upper-case English symbols.
2. The start variable is the symbol .
3. The set of terminals consists of lower-case English symbols.
4. We only consider CFGs with no cycles and no -rules.

A function LRE is implemented, which:

• takes an input string encoding a CFG and returns a string encoding an equivalent CFG which is not left-recursive.

• A string encoding a CFG is a semi-colon separated sequence of items. Each item represents a largest set of rules with the same left-hand side and is a comma-separated sequence of strings. The first string of each item is a member of , representing the common left-hand side. The first string of the first item is .

• For example, consider the CFG ({S,T,L}, {i,a,b,c,d}, R, S), where R is given by the following productions:
  S → ScT | T
  T → aSb | iaLb | i
  L → SdL | S
  This CFG will have the following string encoding: S,ScT,T;T,aSb,iaLb,i;L,SdL,S

• The function LRE will assume the ordering of variables as they appear in the string encoding of the CFG. Thus, in the above example, the variables are ordered thus: S, T, L.

• LRE returns a string encoding the resulting CFG where a newly-introduced variable, for the elimination of immediate left-recursion for variable A, is the string A'. Thus, for the above example, the output should be as follows: S,TS';S',cTS',;T,aSb,iaLb,i;L,aSbS'dL,iaLbS'dL,iS'dL,aSbS',iaLbS',iS'