Skip to content

Latest commit

 

History

History
105 lines (86 loc) · 11.5 KB

README.md

File metadata and controls

105 lines (86 loc) · 11.5 KB

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
    • (ri,wi+1) = ri+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

DFA

  • 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 NFA
  • 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

FDFA

  • 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'