Finite State Machines and Regular Expressions

Posted on Feb 14, 2025 in Commerce

Definitions and Operations

  • To ∈ q ∈ Q and is defined: d(q) = (p / there is a marked transition dqap)
  • d(q) is the collection of states q “continue” to q directly through the transition marked with.
  • Example: (Image would go here – description: visual representation of state transitions)

Inside AFN with Transitions

The AFN without transitions:

  1. Calculate the Epsilon d-closing of all states.
  2. Draw the automaton without initial transitions.
  3. Put transitions: (q) = – c[d(- c(q))] = (p1, p2, …, pn). Draw arrows with the symbol q until all the pi (i = 1, …, n). -> This is done for all states (and in each state is made with all the symbols).

Finite State Machine, Regular Expression

ER -> AF: Base case:

  1. a ∈:

Recursive cases: Having the ER r and s -> L(r) = L(M1) where M1 = (Q1, 1, F1), L(s) = L(m2) where m2 = (Q2, S2, F2)

AF -> ER

d all languages accepted by an AF on the alphabet and the unit contains languages {a} for all a ∈. This set is closed in relation to marriage, meeting and star closure.

  • Kleene’s theorem: Every regular language is accepted by a FA and every language accepted by a FA is also a regular language.

Consider F and M = (Q, P, K) and suppose qs = q0 is the initial state. For any state qi, is: ai = (w ∈ / (qi, w) F) // This is the ai is what is accepted at qi // Note that q0 = L(M) // If I notice, it is also possible that q = i // If qi ∈ F, then is grown q ∈ i.

  • Arden’s lemma: X = A · XUB where A has a unique solution, X = A*B

Properties of Regular Languages

When is a language L regular?

  1. If L is finite, L is regular.
  2. When there is an ER such that R L(r) = L.
  3. If there is an AF M such that L(M) = L.

NOTE: To prove a language is regular -> build the automaton to give the regular expression. // To prove that a language is not regular use the pumping lemma. Suppose we work with a regular language: AFD M = (Q, q0, F) / L(M) is infinite (it told us there will be feedback loops d I close the lock + *) // w = a1 to a2 …. an+1 / w ∈ L(m) // |w| = n+1> n / q0, q1, ….., qn+1 acceptance path d, n+1 states, then some states are repeated in Q n / w = a1 to a2 …. an+1 ∈ L(m) / w’ = a1 to a2 …. aj ak+1 ak+2 …… an n+1 ∈ L(m)

Pumping Lemma: Let L be an infinite regular language, then there exists a constant k associated with the language, so that, if w is a string whose length L is greater than or equal to (|w| >= k), w can be decomposed in the form w = UVX where: |v| >= 1, |uv| <= k, and all strings of the form uvix ∈ L, for all i >= 0. // Arden’s lemma has a property that must have all regular languages and gives us a way to determine whether a language is not regular. To demonstrate it, prove that for any value of n big enough, if there will be, at least one string length at most that fails to be pumped.

The pumping lemma does not say whether a language is regular; it tells us if it is not by finding a counterexample.

Theorem: M is an AF with k states:

  1. L(M) <=> M accepts a string of length less than k.
  2. L(M) infinite <=> M accepts a string of length n, where k <= n < 2k.

// In practice it is simpler given an automaton M:

  1. We can delete all those states in which there is a way to a final state. If you delete the initial state, then L(M) = .
  2. Abolish dead states. If there are still cycles (loops), then L(M) is infinite.

For the complement of a regular language (which is also regular), the AFD can build the original language and then find that of its additional final states by changing the end and vice versa.