Context-free grammars (CFG in short), which were first used in the study of human languages, are a method for describing languages focusing on certain features that have a recursive structure. An important application of context-free grammars is in the specification and compilation of programming languages. Languages generated by context-free grammars are called context-free languages.

The term “automata” comes from the greek word “αυτόματα” and refers to “self-acting” machines designed to automatically perform predetermined sequences of operations. Automata Theory studies how computations are performed by various machines (i.e., computational models) and makes a focal part of any core curriculum in computer science and engineering. In its context, automata are mathematical models for abstract machines which describe what can be done with computers of varying amounts of memory.

Push-Down Automata - PDA in short - describe what can be done with computers of infinite memory though in the limited form of a stack, in a similar way that Turing machines abstract what can be done with ordinary computers. A stack is a “last in, first out” storage device implying that all access to the stack, for both reading and writing, may be done only at the top. PDA describe algorithms by explaining all the different states such procedures can be in, the events that can occur in each state, what actions are taken in response to the events and what transitions happen as a result. Procedures usually start in a particular beginning state and, then, follow a sequence of steps to get it into a regular operating state, and move to other states in response to particular types of input. PDA can be deterministic or nondeterministic depending on whether they can only go to one state from another or have the option to explore multiple states. Pushdown automata are the class of machines recognizing the context-free languages.

Context-free grammars and nondeterministic pushdown automata are equivalent in power, i.e., both are capable of describing the class of context-free languages. There is a particular constructive method for converting any context-free grammar into a pushdown automaton that recognizes the same language. This method is part of the curriculum of courses on Theory of Computation.

In this work, we present an online application - CFG2nPDA - which computes an equivalent nPDA recognizing the language generated by a CFG. More precisely, users provide as input the rules of a CFG generating a language. Then, the application computes and returns as visualized output - also available to download as an image file - an equivalent nPDA via a provably correct constructive procedure. Furthermore, the application enables users to test their own or automatically generated strings for membership in the language generated by the input CFG or, equivalently, recognized by the computed equivalent nPDA. For membership of a string in the language of the CFG, a production for that string is computed and presented on screen. For membership in the language of the nPDA, a detailed step-by-step run is performed on screen and the input string, once read, is recognized (i.e., accepted) by the nPDA only if the machine reaches its final state with an empty stack; otherwise, the input string is rejected.

CFG2nPDA is a responsive and user-friendly educational application developed using Javascript, HTML, CSS and the Graphviz open source graph visualization software.

Keywords: Web application, CFG to nPDA conversion and visualization, Theory of Computation, Automata Theory, html, css, javascript, graphviz.