Traditionally, formal languages are defined as sets of words. More#R##N#recently, the alternative coalgebraic or coinductive representation as#R##N#infinite tries, i.e., prefix trees branching over the alphabet, has#R##N#been used to obtain compact and elegant proofs of classic results in#R##N#language theory. In this paper, we study this representation in the#R##N#Isabelle proof assistant. We define regular operations on infinite#R##N#tries and prove the axioms of Kleene algebra for those#R##N#operations. Thereby, we exercise corecursion and coinduction and#R##N#confirm the coinductive view being profitable in formalizations, as it#R##N#improves over the set-of-words view with respect to proof automation.
['Dmitriy Traytel']
Formal Languages, Formally and Coinductively