{"data":{"kind":"file","path":"README.md","version_id":"bf9ptoqqq3lxb9vrfh56kvr0","entry":{"name":"README.md","path":"README.md","is_directory":false,"size":5694,"modified_at":"2026-08-07T06:30:03.671000","content_hash":"66fb017cf777b62c92e7d1538dc6abfecc278836268712da5408de63ac9ad7a7"},"entries":[],"content":"# sipser-env\r\n\r\nRL environment for **automata and formal languages**, on the topics of *Introduction to the\r\nTheory of Computation* (Sipser).\r\n\r\n- **Tasks:** 27 across 5 categories (dfa 6, nfa 5, regex 5, cfg 6, tm 5)\r\n- **Dataset:** [`sipser-tasks-v1`](https://huggingface.co/datasets/eltociear/sipser-tasks-v1)\r\n- **Reward:** binary, from an exact comparison. No LLM judge, no network, no clock.\r\n- **Dependencies in the sandbox:** none.\r\n\r\n```bash\r\nprime env install eltociear/sipser-env\r\n```\r\n\r\n\r\n27 automata-and-formal-languages tasks for the\r\n[`sipser-env`](https://app.primeintellect.ai/dashboard/environments/eltociear/sipser-env) RL\r\nenvironment, on the topics of *Introduction to the Theory of Computation* (Sipser): DFA and NFA\r\nsimulation, the subset construction, DFA minimisation, regular expressions, CYK parsing of a\r\ncontext-free grammar, and Turing machine execution.\r\n\r\n| field | meaning |\r\n|---|---|\r\n| `task_id` | `sp-000` … `sp-026` |\r\n| `category` | dfa / nfa / regex / cfg / tm |\r\n| `prompt` | the question and the exact shape of the answer |\r\n| `api_description` | the fixed machines — DFA, NFA, CFG, TM — plus the shortlex ordering rule |\r\n| `expected_output` | JSON `{\"rows\": [...]}`, **computed by executing a reference solution** |\r\n\r\nCategories: dfa 6, nfa 5, regex 5, cfg 6, tm 5. No dependencies — `itertools` and `re` are\r\nstandard library.\r\n\r\n## Original machines, not the book's exercises\r\n\r\nNothing is copied. The automata, grammar and Turing machine are invented here — deliberately\r\nincluding the grammar, because the CYK example printed in most textbooks is one and the same\r\nand its parse table is all over the web. A model can recall that table; it cannot recall this\r\none.\r\n\r\n## Why automata theory suits an executed answer key\r\n\r\nThese questions look like proofs but are almost all **decidable by simulation**. Whether a DFA\r\naccepts a string, how many strings of length n it accepts, how many subsets the construction\r\nreaches, whether a regular expression and an automaton describe the same language, whether a\r\ngrammar generates a string and with how many parse trees — each is a program, and the answer is\r\nwhatever the program computes.\r\n\r\n## The trap: \"how many states?\" has three right answers\r\n\r\nFor the NFA here, the subset construction has **8** subsets on paper, **4** are reachable, and\r\n**3** survive minimisation. All three are correct answers to differently-worded questions, and\r\nan environment that was vague about which it wanted would mark correct work wrong. Every task\r\nnames the one it means, and one task asks for all three at once.\r\n\r\n## A defect caught before publishing\r\n\r\nA parse-tree-counting task asked how many trees the grammar gives to `baaba` — a string the\r\ngrammar **does not generate at all**, so the answer was `0` and the task taught nothing about\r\nambiguity. It now asks about `bbabb` (3 trees), `aaaab` (2) and `ba` (0), so one row\r\ndistinguishes ambiguous, derivable and non-generated. The builder asserts exactly that.\r\n\r\nThe two machines' languages are also cross-checked by brute force over every string up to\r\nlength 10, rather than being trusted from their state diagrams.\r\n\r\nVerify with `python environments/sipser_env/build_tasks.py --verify` (27/27).\r\nSource: <https://github.com/eltociear/my-molt-agent/tree/main/environments/sipser_env>\r\n\r\n## Environment arguments\r\n\r\n`load_environment()` deliberately exposes very little: the program's guidance is that an\r\nenvironment should have one correct way to be run, so nothing about the prompts, the parsing or\r\nthe grading is configurable.\r\n\r\n| Argument | Default | Meaning |\r\n|---|---|---|\r\n| `split` | `'train'` | Dataset split to load. |\r\n| `dataset_name` | `'eltociear/sipser-tasks-v1'` | Hugging Face dataset of tasks. Change only to point at a fork. |\r\n| `max_turns` | `5` | Tool-use turns the model gets before the rollout ends. |\r\n| `**kwargs` | — | Passed through to the underlying `SandboxEnv`. |\r\n\r\n## Reward rubric\r\n\r\n| Reward function | Weight | What it returns |\r\n|---|---|---|\r\n| `correctness` | 1.0 | Binary: 1.0 when the answer matches the reference, else 0.0. |\r\n\r\nThere is no LLM judge and no partial credit. The score is computed on the host in\r\n`post_rollout` and read back by the rubric, so the reward is a deterministic function of the\r\nvalues the model left in `result`. A **harness** failure (dead sandbox, unreadable read-back)\r\nalso scores 0.0 but additionally sets `state[\"scoring_error\"]`, so an eval run can tell a\r\nbroken harness from a wrong answer instead of blaming the model.\r\n\r\n## Dependencies\r\n\r\n`datasets>=4.1.0`, `verifiers>=0.1.8`\r\n\r\n## Sample `vf-eval` usage\r\n\r\n```bash\r\nuv run vf-install sipser-env\r\nuv run vf-eval -s sipser-env -m gpt-4.1 -n 5 -r 3\r\nuv run vf-tui                      # inspect the outputs/ folder it writes\r\n```\r\n\r\n## Known limitation\r\n\r\nThe Docker **sandbox transport** has not been executed — `docker run`, `pip install`, and the\r\nmodel's code running inside the container — because that needs a Docker runtime and an\r\ninference provider key, neither available where this was authored.\r\n\r\nEverything else is exercised. `environments/test_scoring_path.py` runs this environment's\r\n`post_rollout` and `Rubric` with the sandbox mocked out, asserting that a correct answer scores\r\n1.0, a well-formed wrong answer scores 0.0, and a dead sandbox scores 0.0 *and* sets\r\n`scoring_error` so a harness failure is never mistaken for a bad model. It also checks that\r\nwhat `build_tasks.py` emits is exactly what the scorer expects. The environment mirrors the\r\nstructure of `polars_env` (already accepted into the Environments Program) and imports cleanly\r\nagainst `verifiers` 0.2.1.\r\n","encoding":"utf-8","truncated":false,"total_bytes":5694},"status":null}