app.py

"""
PDA Simulator - Flask Backend
Theory of Computation Visual Tool
"""

from flask import Flask, render_template, request, jsonify
import json
import re

app = Flask(__name__)

# ─────────────────────────────────────────────
#  Sample PDA definitions
# ─────────────────────────────────────────────
SAMPLE_PDAS = {
    "anbn": {
        "name": "aⁿbⁿ Language",
        "description": "Accepts strings of the form aⁿbⁿ where n ≥ 1",
        "states": ["q0", "q1", "q2"],
        "input_alphabet": ["a", "b"],
        "stack_alphabet": ["Z", "A"],
        "start_state": "q0",
        "initial_stack": "Z",
        "final_states": ["q2"],
        "acceptance": "final_state",
        "transitions": [
            "q0, a, Z -> q0, AZ",
            "q0, a, A -> q0, AA",
            "q0, b, A -> q1, ε",
            "q1, b, A -> q1, ε",
            "q1, ε, Z -> q2, Z"
        ],
        "test_strings": ["ab", "aabb", "aaabbb", "aab", "abb"]
    },
    "balanced_parens": {
        "name": "Balanced Parentheses",
        "description": "Accepts strings with balanced ( and ) brackets",
        "states": ["q0", "q1"],
        "input_alphabet": ["(", ")"],
        "stack_alphabet": ["Z", "P"],
        "start_state": "q0",
        "initial_stack": "Z",
        "final_states": ["q1"],
        "acceptance": "final_state",
        "transitions": [
            "q0, (, Z -> q0, PZ",
            "q0, (, P -> q0, PP",
            "q0, ), P -> q0, ε",
            "q0, ε, Z -> q1, Z"
        ],
        "test_strings": ["()", "(())", "((()))", ")(", "(()", "(())()"]
    },
    "wcwr": {
        "name": "wcwᴿ Palindrome",
        "description": "Accepts strings of the form wcwᴿ where w∈{a,b}*",
        "states": ["q0", "q1", "q2"],
        "input_alphabet": ["a", "b", "c"],
        "stack_alphabet": ["Z", "A", "B"],
        "start_state": "q0",
        "initial_stack": "Z",
        "final_states": ["q2"],
        "acceptance": "final_state",
        "transitions": [
            "q0, a, Z -> q0, AZ",
            "q0, a, A -> q0, AA",
            "q0, a, B -> q0, AB",
            "q0, b, Z -> q0, BZ",
            "q0, b, A -> q0, BA",
            "q0, b, B -> q0, BB",
            "q0, c, Z -> q1, Z",
            "q0, c, A -> q1, A",
            "q0, c, B -> q1, B",
            "q1, a, A -> q1, ε",
            "q1, b, B -> q1, ε",
            "q1, ε, Z -> q2, Z"
        ],
        "test_strings": ["acа", "abcba", "aabcbaa", "abc", "abcab"]
    }
}

# ─────────────────────────────────────────────
#  PDA Simulator Core Logic
# ─────────────────────────────────────────────

def parse_transitions(transition_lines):
    """
    Parse transition lines like:
      q0, a, Z -> q0, AZ
      q0, ε, Z -> q1, Z
    Returns dict: (state, input_sym, stack_top) -> list of (next_state, push_str)
    """
    transitions = {}
    errors = []
    for i, line in enumerate(transition_lines):
        line = line.strip()
        if not line:
            continue
        # Support -> or →
        line = line.replace('→', '->')
        if '->' not in line:
            errors.append(f"Line {i+1}: Missing '->' in '{line}'")
            continue
        left, right = line.split('->', 1)
        left_parts = [p.strip() for p in left.split(',')]
        right_parts = [p.strip() for p in right.split(',')]
        if len(left_parts) != 3 or len(right_parts) != 2:
            errors.append(f"Line {i+1}: Invalid format in '{line}'")
            continue
        cur_state, inp_sym, stack_top = left_parts
        next_state, push_val = right_parts
        # Normalize epsilon
        inp_sym = '' if inp_sym in ('ε', 'eps', 'epsilon', '') else inp_sym
        push_val = '' if push_val in ('ε', 'eps', 'epsilon') else push_val
        key = (cur_state, inp_sym, stack_top)
        if key not in transitions:
            transitions[key] = []
        transitions[key].append((next_state, push_val))
    return transitions, errors


def simulate_pda(states, start_state, final_states, initial_stack,
                 transitions, input_string, acceptance_mode, max_steps=500):
    """
    BFS/DFS simulation of PDA. Returns list of step configurations.
    Each config: {step, state, remaining_input, stack, transition_applied, status}
    """
    # Each item: (state, remaining_input, stack_list, history_of_steps)
    initial_config = (start_state, list(input_string), [initial_stack], [])
    queue = [initial_config]
    visited = set()
    accepting_path = None
    all_paths_tried = []

    step_counter = 0

    while queue and step_counter < max_steps:
        step_counter += 1
        state, remaining, stack, history = queue.pop(0)

        # Avoid infinite loops via visited states
        visit_key = (state, tuple(remaining), tuple(stack))
        if visit_key in visited:
            continue
        visited.add(visit_key)

        inp_sym = remaining[0] if remaining else ''
        stack_top = stack[-1] if stack else ''

        current_step = {
            "step": len(history) + 1,
            "state": state,
            "remaining_input": ''.join(remaining) if remaining else 'ε',
            "stack": list(stack),
            "transition_applied": None,
            "status": "running"
        }

        # Check acceptance
        if acceptance_mode == "final_state":
            if not remaining and state in final_states:
                accepting_path = history + [current_step]
                accepting_path[-1]["status"] = "accepted"
                break
        elif acceptance_mode == "empty_stack":
            if not remaining and not stack:
                accepting_path = history + [current_step]
                accepting_path[-1]["status"] = "accepted"
                break

        # Try epsilon transitions first, then input transitions
        moved = False
        for try_inp in (['', inp_sym] if inp_sym else ['']):
            key = (state, try_inp, stack_top)
            if key in transitions:
                for next_state, push_val in transitions[key]:
                    new_remaining = remaining[1:] if try_inp else remaining
                    new_stack = stack[:-1]  # pop stack top
                    # Push new symbols (push_val reversed onto stack)
                    if push_val:
                        for ch in reversed(push_val):
                            new_stack.append(ch)
                    transition_label = f"({state}, {'ε' if not try_inp else try_inp}, {stack_top}) → ({next_state}, {'ε' if not push_val else push_val})"
                    step_info = dict(current_step)
                    step_info["transition_applied"] = transition_label
                    new_history = history + [step_info]
                    queue.append((next_state, new_remaining, new_stack, new_history))
                    moved = True

        if not moved:
            # Dead configuration
            dead_step = dict(current_step)
            dead_step["status"] = "dead"
            all_paths_tried.append(history + [dead_step])

    if accepting_path:
        return {"accepted": True, "steps": accepting_path}
    else:
        # Return the longest dead path for informative output
        if all_paths_tried:
            longest = max(all_paths_tried, key=len)
        else:
            longest = [{"step": 1, "state": start_state,
                        "remaining_input": input_string or 'ε',
                        "stack": [initial_stack],
                        "transition_applied": None, "status": "dead"}]
        if longest:
            longest[-1]["status"] = "rejected"
        return {"accepted": False, "steps": longest}


# ─────────────────────────────────────────────
#  Flask Routes
# ─────────────────────────────────────────────

@app.route('/')
def index():
    return render_template('index.html')


@app.route('/api/samples', methods=['GET'])
def get_samples():
    """Return list of sample PDA names and keys."""
    result = {}
    for key, val in SAMPLE_PDAS.items():
        result[key] = {k: v for k, v in val.items()}
    return jsonify(result)


@app.route('/api/simulate', methods=['POST'])
def simulate():
    """
    Simulate PDA.
    Expects JSON body with PDA definition and input string.
    """
    data = request.get_json()
    if not data:
        return jsonify({"error": "No JSON body provided"}), 400

    # Extract fields
    states_raw = data.get('states', '')
    input_alpha_raw = data.get('input_alphabet', '')
    stack_alpha_raw = data.get('stack_alphabet', '')
    start_state = data.get('start_state', '').strip()
    initial_stack = data.get('initial_stack', '').strip()
    final_states_raw = data.get('final_states', '')
    transitions_raw = data.get('transitions', [])
    input_string = data.get('input_string', '')
    acceptance_mode = data.get('acceptance', 'final_state')

    # Parse comma-separated fields
    states = [s.strip() for s in states_raw.split(',') if s.strip()]
    final_states = [s.strip() for s in final_states_raw.split(',') if s.strip()]

    # Validate
    errors = []
    if not states:
        errors.append("States cannot be empty.")
    if not start_state:
        errors.append("Start state cannot be empty.")
    if start_state and start_state not in states:
        errors.append(f"Start state '{start_state}' not in states list.")
    if not initial_stack:
        errors.append("Initial stack symbol cannot be empty.")
    for fs in final_states:
        if fs not in states:
            errors.append(f"Final state '{fs}' not in states list.")

    # Parse transitions
    if isinstance(transitions_raw, list):
        transition_lines = transitions_raw
    else:
        transition_lines = transitions_raw.split('\n')

    transitions, parse_errors = parse_transitions(transition_lines)
    errors.extend(parse_errors)

    if errors:
        return jsonify({"error": " | ".join(errors)}), 400

    # Run simulation
    result = simulate_pda(
        states=states,
        start_state=start_state,
        final_states=final_states,
        initial_stack=initial_stack,
        transitions=transitions,
        input_string=input_string,
        acceptance_mode=acceptance_mode
    )

    # Build transitions list for diagram
    diagram_transitions = []
    for (cur_state, inp_sym, stack_top), targets in transitions.items():
        for next_state, push_val in targets:
            diagram_transitions.append({
                "from": cur_state,
                "to": next_state,
                "label": f"{'ε' if not inp_sym else inp_sym}, {stack_top}/{'ε' if not push_val else push_val}"
            })

    result["diagram"] = {
        "states": states,
        "start_state": start_state,
        "final_states": final_states,
        "transitions": diagram_transitions
    }
    result["total_steps"] = len(result["steps"])

    return jsonify(result)


@app.route('/api/validate', methods=['POST'])
def validate():
    """Quick validation endpoint."""
    data = request.get_json()
    transitions_raw = data.get('transitions', [])
    if isinstance(transitions_raw, list):
        lines = transitions_raw
    else:
        lines = transitions_raw.split('\n')
    _, errors = parse_transitions(lines)
    return jsonify({"valid": len(errors) == 0, "errors": errors})


if __name__ == "__main__":
    app.run(host="0.0.0.0", port=7860, debug=True)