FSA-to-RegExp

Was created as homework for Theoretical Computer Science course at Innopolis University.

Description

Given an FSA description in the

Input file format

states=[s1,s2,...]	  // s1 , s2, ... ∈ latin letters, words and numbers
alpha=[a1,a2, ...]	  // a1 , a2, ... ∈ latin letters, words, numbers and character '_’(underscore)
init.st=[s]	          // s ∈ states
fin.st=[s1,s2,...]	  // s1, s2 ∈ states
trans=[s1>a>s2,... ]  // s1,s2,...∈ states; a ∈ alpha

Validation result

Errors:

• E0: Input file is malformed
• E1: A state 's' is not in the set of states
• E2: Some states are disjoint
• E3: A transition 'a' is not represented in the alphabet
• E4: Initial state is not defined
• E5: FSA is nondeterministic

Kleene's Algorithm

It transforms a given deterministic finite state automaton (FSA) into a regular expression.

Given an FSA M = (Q, A, δ, q₀, F), with Q = {q₀, . . . , q_n} its set of states, the algorithm computes:

• the sets R_ij^k of all strings that take M from state q_i to q_j without going through any state numbered higher than k
• each set R_ij^k is represented by a regular expression
• the algorithm computes them step by step for k = −1, 0, ... , n
• since there is no state numbered higher than n, the regular expression R_0jⁿ represents the set of all strings that take M from its start state q₀ to q_j
  • If F = {q₁, ... , q_f} is the set of accept states, the regular expression R₀₁ⁿ| ... |R_0fⁿ represents the language accepted by M

The initial regular expression, for k = -1, are computed as:

• R_ij^-1 = a₁ | ... | a_m if i ≠ j, where δ(q_i, a₁) = ... = δ(q_i, a_m) = q_j
• R_ij^-1 = a₁ | ... | a_m | Ɛ if i = j, where δ(q_i, a₁) = ... = δ(q_i, a_m) = q_j

After that, in each step the expressions R_ij^k are computed from the previous ones by:

• R_ij^k = R_ik^k-1(R_kk^k-1)*R_kj^k-1|R_ij^k-1

The Kleene’s Algorithm should be used as presented above, but with following modifications:

• Denote ∅ as
  {}
• Denote Ɛ as
  eps
• Define update rule with the additional parentheses: R_ij^k = (R_ik^k-1)(R_kk^k-1)*(R_kj^k-1)|(R_ij^k-1)