Starting DFA and NFA using Pyformlang

https://pyformlang.readthedocs.io/en/latest/

A Deterministic Finite Automaton (DFA) is a theoretical model of computation used to recognize regular languages. A DFA consists of:

• A finite set of states.

• A finite set of input symbols (alphabet).

• A transition function that maps state-symbol pairs to a new state.

• A start state.

• A set of accepting (final) states.

A DFA processes a string character by character and either accepts or rejects it based on the final state.

---

Simple DFA Example using pyformlang

Let's start with a DFA that accepts strings containing an even number of 'a's (e.g., "", "aa", "aaaa", "baab", etc.).

Implementation:

from pyformlang.finite_automaton import DeterministicFiniteAutomaton, State, Symbol

# Define states
q0 = State(0)  # Even number of 'a's (Start/Accepting state)
q1 = State(1)  # Odd number of 'a's

# Define input symbols
a = Symbol("a")
b = Symbol("b")  # Any other symbol

# Create DFA
dfa = DeterministicFiniteAutomaton()

# Set start state
dfa.add_start_state(q0)

# Set accepting state(s)
dfa.add_final_state(q0)

# Define transitions
dfa.add_transition(q0, a, q1)  # 'a' flips state
dfa.add_transition(q1, a, q0)  # 'a' flips back
dfa.add_transition(q0, b, q0)  # 'b' doesn't change state
dfa.add_transition(q1, b, q1)  # 'b' doesn't change state

# **Test the DFA**
def test_string(s):
    return dfa.accepts([Symbol(c) for c in s])

# **Example Tests**
inputstrings=["","aa","aba","abba"]
for inputstring  in inputstrings:
    if test_string(inputstring):
        print(inputstring," is accepted")
    else:
        print(inputstring," is not accepted")

 # True

---

Explanation

1. States: We use two states:

   • q0: Represents an even count of 'a's (starting state, accepting state).

   • q1: Represents an odd count of 'a's.

2. Transitions:

   • a flips between q0 and q1.

   • Any other character (b) keeps the current state unchanged.

3. Acceptance: A string is accepted if it ends in q0 (even number of 'a's).

This is a simple introduction to DFA using pyformlang. Let me know if you need more details! 🚀Pyformlang

DFA Problems:

1. DFA for odd number of 'b's

   • Design a DFA that accepts strings containing an odd number of 'b's over the alphabet {a, b}.

2. DFA for "aa" as a substring

   • Create a DFA that accepts all strings that contain "aa" as a substring.

3. DFA for strings not ending with "ab"

   • Construct a DFA that rejects any string that ends with "ab".

4. DFA for length exactly 3

   • Build a DFA that accepts only strings of length exactly 3 over {a, b}.

5. DFA for "a" at even positions

   • Design a DFA that accepts strings where every 'a' appears at an even index (1-based index).