Trustworthy Systems

A mechanisation of some context-free language theory in HOL4

Authors

Aditi Barthwal and Michael Norrish

Australian National University

NICTA

Abstract

We describe the mechanisation of some foundational results in the theory of context-free languages (CFLs), using the HOL4 system. We focus on pushdown automata (PDAs). We show that two standard acceptance criteria for PDAs (“accept-by-empty-stack” and “accept-by-final-state”) are equivalent in power. We are then able to show that the pushdown automata (PDAs) and context-free grammars (CFGs) accept the same languages by showing that each can emulate the other. With both of these models to hand, we can then show a number of basic, but important results. For example, we prove the basic closure properties of the context-free languages such as union and concatenation. Along the way, we also discuss the varying extent to which textbook proofs (we follow Hopcroft and Ullman) and our mechanisations diverge: sometimes elegant textbook proofs remain elegant in HOL; sometimes the required mechanisation effort blows up unconscionably.

BibTeX Entry

  @article{Barthwal_Norrish_14,
    author           = {Barthwal, Aditi and Norrish, Michael},
    doi              = {10.1016/j.jcss.2013.05.003},
    journal          = {Journal of Computer and System Sciences},
    keywords         = {context-free languages, language theory},
    month            = mar,
    number           = {2},
    pages            = {346--362},
    paperurl         = {https://trustworthy.systems/publications/nicta_full_text/7411.pdf},
    title            = {A mechanisation of some context-free language theory in {HOL4}},
    volume           = {80},
    year             = {2014}
  }

Download