A mechanisation of some context-free language theory in HOL4
Barthwal, Aditi; Norrish, Michael
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,...[Show more]
|Collections||ANU Research Publications|
|Source:||Journal of Computer and System Sciences|
|01_Barthwal_A_mechanisation_of_some_2014.pdf||269.73 kB||Adobe PDF||Request a copy|
Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.
Updated: 17 November 2022/ Responsible Officer: University Librarian/ Page Contact: Library Systems & Web Coordinator