রেগুলার এক্সপ্রেশন — ফরমাল ডেফিনিশন

def language_of(node, max_length):
    """genuinely computes L(R) up to a length bound, via structural recursion on the regex AST
    (nested tuples) -- never uses Python's `re` module."""
    kind = node[0]

    if kind == "empty":
        return set()
    if kind == "eps":
        return {""}
    if kind == "sym":
        a = node[1]
        return {a} if len(a) <= max_length else set()
    if kind == "union":
        _, R, S = node
        return language_of(R, max_length) | language_of(S, max_length)
    if kind == "concat":
        _, R, S = node
        LR = language_of(R, max_length)
        LS = language_of(S, max_length)
        return {x + y for x in LR for y in LS if len(x) + len(y) <= max_length}
    if kind == "star":
        _, R = node
        LR = {w for w in language_of(R, max_length) if w != ""}
        result = {""}
        frontier = {""}
        while frontier:
            new = set()
            for s in frontier:
                for r in LR:
                    cand = s + r
                    if len(cand) <= max_length and cand not in result:
                        new.add(cand)
            result |= new
            frontier = new
        return result
    raise ValueError(f"unknown regex node: {node}")


# regex (a U b)* a  as nested tuples
regex = ("concat",
         ("star", ("union", ("sym", "a"), ("sym", "b"))),
         ("sym", "a"))

MAX_LEN = 3
lang = language_of(regex, MAX_LEN)
print(f"L((a∪b)*a) up to length {MAX_LEN}:", sorted(lang, key=lambda w: (len(w), w)))

# hand-verification: every generated string over {a,b} up to length 3 that ends in 'a'
from itertools import product
expected = set()
for length in range(0, MAX_LEN + 1):
    for combo in product("ab", repeat=length):
        s = "".join(combo)
        if s.endswith("a"):
            expected.add(s)

print("expected set (strings ending in 'a', length<=3):", sorted(expected, key=lambda w: (len(w), w)))
assert lang == expected
print("regex-generated ভাষা এবং হাতে-গোনা 'a'-এ শেষ হওয়া স্ট্রিং সেট হুবহু মিলেছে।")

# sanity checks on base cases
assert language_of(("empty",), 3) == set()
assert language_of(("eps",), 3) == {""}
assert language_of(("sym", "a"), 3) == {"a"}
assert language_of(("union", ("sym", "a"), ("sym", "b")), 3) == {"a", "b"}
print("বেস কেসগুলোও সঠিক।")