M.Sc. in Computer Science
Enrolled / Active Graduate Candidate
Graduate coursework and research specializing in computability theory, distributed systems, advanced automata, edge cloud computing architectures, and data engineering.
Graduate Seminar Paper & Presentation
Advanced Theory of Computation (Computability and Formal Models)
The Chomsky Hierarchy & The Relative Power of Formal Language Models
Theoretical Foundations, Machine Separations, Complexity Limits, and Contemporary Computing Applications
Abstract & Investigation Scope:
Comprehensive graduate research investigation into the four classical tiers of formal language theory: Regular (Type 3), Context-Free (Type 2), Context-Sensitive (Type 1), and Unrestricted (Type 0). Establishes how memory topologies (none, LIFO stack, linearly bounded tape, and infinite tape) govern computational expressivity, provides adversarial Pumping Lemma separation proofs, analyzes decidability boundaries, and demonstrates practical impacts on compiler pipelines, Language-Theoretic Security (LangSec), and Transformer expressivity limits.
Core Highlights & Findings
- Rigorous non-pumping adversarial proofs separating Level 3 (0ⁿ1ⁿ ∉ REG) and Level 2 (aⁿbⁿcⁿ ∉ CFL)
- Linear Bounded Automata (LBA) space-bounded configuration analysis & Immerman-Szelepcsényi complementation
- Language-Theoretic Security (LangSec): Formal analysis of why ad-hoc parsing creates exploitable "weird machines"
- Diagnostic evaluation of Transformer soft-attention circuit bounds (TC⁰) against formal language recognition
Formal Hierarchy Breakdown
- Type 3 (Regular): DFA / NFA / RegEx • No memory • $O(n)$ time • Fully Decidable
- Type 2 (Context-Free): Pushdown Automata (PDA) • LIFO Stack memory • $O(n^3)$ CYK
- Type 1 (Context-Sensitive): Linear Bounded Automata (LBA) • Tape $\le n$ • PSPACE-complete
- Type 0 (Unrestricted): Turing Machine • Infinite Tape • Turing-Complete (Undecidable)
Automata Theory
Chomsky Hierarchy
Pumping Lemmas
LangSec
Compiler Design
Decidability
