FSA-to-RegExp

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

Description

Given an FSA description in the input.txt, your program should output the output.txt containing an error description or a regular expression that corresponds to the given FSA. The regular expression should be built according to a slightly modified version of the Kleene’s algorithm.

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)