Formal Language Typing Game — Theory of Computation · Tkinter

type

Theory of Computation

status

Completed

year

2024

role

Solo Developer

01 —

System Architecture · 3D View

02 —

Architecture Diagram

Tkinter Window

TypingGame class

↓

Entry Widget

Keyboard · Return key

↓

Sentence Picker

random.choice · 9 sets

45s Timer

root.after(1000)

↓

DFA / Regex

re.match · 7 patterns

Stack PDA

Balanced parentheses

Palindrome

String reversal

↓

Score Engine

+10 correct · -5 wrong

Feedback Label

✔️ Correct / ❌ Wrong

03 —

Screenshots & Output

terminal

$ python3 Toc_final.py

Formal Language Typing Game — Theory of Computation

Pattern: a*b* Timer: 45s

Input aaaabbbb → re.match a*b* → VALID +10

Pattern: balanced_parentheses

Input (()) → Stack PDA → push push pop pop → empty +10

Input (()( → Stack not empty → INVALID -5

Pattern: palindrome

Input racecar → reversed == original → VALID +10

Final Score: 35 · Time expired · 3/4 correct

Game Session

Live typing validation terminal log

Pattern Accuracy

a*b* / a+b+c+92%

Balanced Parens88%

Palindrome95%

Alternating 0179%

Contains 10184%

Pattern Accuracy

Per-pattern validation scores

Data Output

{
# 9 patterns from Toc_final.py
a_star_b_star: DFA via regex ^a*b*$,
balanced_parens: PDA stack,
palindrome: s == s reversed,
alternating_01: regex ^(01)*$,
# scoring: +10 correct, -5 wrong, 45s timer
}

Automata Config

9-pattern language definitions

Project Structure

📄 Toc_final.py single file ~140 lines

class TypingGame:

├─ __init__ UI setup · 9 sentences

├─ start_game Reset state · 45s timer

├─ validate_sentence DFA · PDA · Palindrome

└─ end_game Disable · show restart

stdlib only: tkinter · re · random · time

Source File

Toc_final.py single-file structure

04 —

What I Built

›

Built a Tkinter desktop game for Theory of Computation coursework that validates 9 formal language patterns in real-time as the player types.

›

Implemented DFA-equivalent validators using Python regex (re module): a*b*, alternating 01, contains 101, ends in 01, a+b+c+, a*b*c*, a*b+c+.

›

Built a stack-based PDA from scratch (no libraries) to validate balanced parentheses — pushes ( and pops on ), returns True only if stack is empty.

›

Implemented palindrome detection using Python string reversal (sentence == sentence[::-1]) as a third automaton class.

›

Scoring system awards +10 for correct answers, deducts -5 for wrong, with a 1-second delay before advancing on failure.

›

Random sentence selection without repetition (tracks used_sentences), skip button, and real-time ✔️/❌ feedback labels.

›

Pure Python with zero external dependencies — only stdlib tkinter and re modules used.

05 —

Project Insights

✎Personal Notes & Learnings

Markdown Editor

### Course Context

Built for **Theory of Computation** at Lawrence Technological University — the goal was to make abstract automata theory tangible through play.

### The 9 Language Patterns

- `a*b*` — zero or more as followed by zero or more bs (DFA via regex)
- `balanced_parentheses` — stack-based PDA, stack must be empty at end
- `palindrome` — string equals its reverse (e.g. "racecar")
- `alternating_01` — matches `(01)*` — strictly alternating
- `contains_101` — any string containing the substring 101
- `ends_in_01` — any binary string ending in 01
- `a+b+c+` — one or more of each, in order
- `a*b*c*` — zero or more of each, in order
- `a*b+c+` — zero as, at least one b and one c

### Key Implementation Details

- Stack PDA built without libraries: iterates char by char, push on `(`, pop on `)`, reject if pop on empty stack
- `used_sentences` list prevents repetition until all 9 are exhausted, then resets
- Timer uses `root.after(1000, self.update_clock)` — Tkinter-native, no threading
- Wrong answers get a 1-second delay (`root.after(1000, self.next_sentence)`) to let feedback register

### What I Learned

- Stack machines and regex are more powerful to implement than they look on paper
- Tkinter event loop model requires careful state management to avoid race conditions

Live Preview

Course Context

Built for Theory of Computation at Lawrence Technological University — the goal was to make abstract automata theory tangible through play.

The 9 Language Patterns

a*b* — zero or more as followed by zero or more bs (DFA via regex)
balanced_parentheses — stack-based PDA, stack must be empty at end
palindrome — string equals its reverse (e.g. "racecar")
alternating_01 — matches (01)* — strictly alternating
contains_101 — any string containing the substring 101
ends_in_01 — any binary string ending in 01
a+b+c+ — one or more of each, in order
a*b*c* — zero or more of each, in order
a*b+c+ — zero as, at least one b and one c

Key Implementation Details

Stack PDA built without libraries: iterates char by char, push on (, pop on ), reject if pop on empty stack
used_sentences list prevents repetition until all 9 are exhausted, then resets
Timer uses root.after(1000, self.update_clock) — Tkinter-native, no threading
Wrong answers get a 1-second delay (root.after(1000, self.next_sentence)) to let feedback register

What I Learned

Stack machines and regex are more powerful to implement than they look on paper
Tkinter event loop model requires careful state management to avoid race conditions

✓ Insights saved locally

← PreviousBuffer Overflow Attack Lab

All Projects

Next →Global Harvest Imports