Day #5 on JFLAP

Today I read chapters 5 of 6 of the Linz book. Chapter 5 talks about context-free languages. Context-free language is a broader set of languages which is able to represent programming languages syntaxes, as opposed to regular languages only able to represent certain tokens. Regular language is a subset of context-free language. Further, I learned about parsing and ambiguity in 5.2 and how to use derivation trees to check ambiguity.

Chapter 6 is simplification of context-free grammars and normal forms of them. To simplify a context-free grammar, there are three goals: no unit productions, no useless variables, and no λ-productions. It is proved in the book that every context-free grammar can be transformed to achieve these three goals. Then the book gives definitions for two common normal forms: Chomsky Normal Form, which has at most two variables on the right side, and Greibach Normal Form, in which all productions have the form A → ax, where a is a terminal symbol and x is a star-union of variables. According to the book, Chomsky form is helpful for testing membership. I am still a little confused with this membership-testing algorithm, but I will be able to understand it.

The next chapter is about Pushdown Automata, which is similar to Finite Automata. The relationship between FA and regular languages is similar to the relationship between Pushdown Automata and context-free languages. I will read about this in the weekend.

I also read one paper by Shaffer that introduces JSAV library on which OpenDSA project is built on. Citation and summary can be found here. There goes my first week on JFLAP. Can’t wait to start coding!


Karavirta, Ville and Shaffer, Clifford A. JSAV: The JavaScript Algorithm Visualization Library. ITiCSE Proceedings of the 18th ACM conference on Innovation and technology in computer science education (2013) 159-164

This paper introduces JSAV as a JavaScript library to implement algorithm visualizations. In the introduction the authors point out different levels of engagement in algorithm visualizations, and in the next section they illustrate how JSAV is able to achieve those interactions in detail. First, JSAV can present static images as well as modifying them without difficulties. Second, JSAV can provide slide-show functionalities, which can be used to make eTextbook. Last but not least, JSAV is able to offer different levels of feedbacks to students. The paper also talks briefly about the OpenDSA project, a eTextbook project aiming to help with DSA (Data Structures and Algorithms) education. OpenDSA project is built based on the development of JSAV.

The development of online version of JFLAP depends heavily on JSAV, so it is essential for me to understand the design patterns and concepts behind JSAV. The product that I contribute to this summer should conform to the general patterns of other eTextbooks in the OpenDSA projects.

Leave a Reply

Your email address will not be published. Required fields are marked *