Day 2 Week 2 on JFLAP

Today I added this wonderful feature into FATester – right-click menu! Now you can right click a node to toggle initial and final states. Sadly, I spent most of the time debugging. There are three main things that I learned today to remember:

1. jQuery selector returns an object different from a normal javascript object. When I used selector to select a node in the graph, the object returned can not simply be operated with methods provided by JSAV.

2. if an event is binded to an object for multiple times, the event will trigger the function as many times as the event is binded. This bothered me when I was trying to toggle initial and final states by clicking a button. If a state is toggle twice, then it is back to its original state!

3. offsets culumate. To make the right click menu appear, I am using a div and setting its position as absolute. However, I first used offset() function to do this, which made the menu move further and further to right and bottom. After searching online, I decided to switch to jQuery function .css() and changed the left and top attributes, which work as a charm.

 

Some screenshots of this new function:

earlier version

Before I developed this new function, users have to click Edit Node button and then click a node to change initial and final states.

toggle initial

Toggle initial state

toggle final

Toggle final state

toggle final

Having two initial states is not allowed

 

Besides this new function, I also added some exercises in the Linz book to the tester. There are now four problems and some test cases.

Day 1 Week 2 on JFLAP

Over the weekend I read chapter 7 of the Linz book. It is about Pushdown Automata. The major difference between Pushdown Automata and DFA is that PA uses a stack to hold relevant information. There are two kinds of PA, nondeterministic and deterministic. Generally, nondeterministic pushdown automata (NPDA) are used more frequently. Edges in NPDA include three pieces of information: input variable, top element in the stack, and element to replace the top of the stack. NPDA is proved to be equivalent to context-free grammars and context-free languages. There is a part in JFLAP that lets you transfrom from one to another.

Today is a day to celebrate: my office is finally ready! I have a big monitor in there. I spent most of my day implementing a Finite State Machine tester. This tester is modified from FAEditor created by Martin last summer. The tester, as shown below in a screenshot, is able to provide a whole exercise set. Clicking on different question indices will lead to different questions. Students are able to either create a new machine with the editor or load one from local machine. After they finish, the “test” button will begin the tests and the results are shown at the bottom of the page. Test cases, standard answers and test results are provided, just like how Duke CS classes’ APT testers. Test cases are provided because I believe it is harder for students to “hard code” them in the machine than to actually think about the problems.

FATester screenshot

Test problems are imported from a JSON file which can be modified by instructors. There will probably also be an exercise problem editor, in which users can create problems and save in JSON format. JSON file is read synchronously, because the exercise may only continue after the problems are loaded! I totally ignored the warning from jQuery about doing so would be detrimental to user experience. I had no choice. Another challenge that I faced was integrating the multiple problem feature. I solved it using a variable to store current exercise, and created an update function to update user interface and the tester.

Tomorrow I will probably be working on the problem editor, or implement a new kind of exercise.

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!

Reading:

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.

Day #4 on JFLAP

Today I read three papers in the morning. One is about the difficulties students experience when learning formal languages and automata theory; one is a proposal during a conference that advocates XML-based tools development to visualize algorithms; the last one is about the available softwares there are in the field of algorithm visualization. Formal references and summareis are here.

I then downloaded all the code written by Martin and Sung-hoon last summer. Specifically I perusedFAEditor.js and FATraversal.js. I now understand the big structure of what they built and common tricks of doing things. This will help me in later work for sure.

One problem that I notice with JSAV library is that the arrows are too small to see. I visited the documentation of JSAV again but did not find any configuration options. Professor Rodger said she will complain this to the organization.

Later in the afternoon I updated the website to separate readings from blogs because I realize reading summaries kind of mess up with blogs. Right now there are “Blog” and “Reading” buttons on the navigation bar. Before there was only one “Blog” button. With a little effor, I also used jQuery to include the same header html in every page so I don’t have to copy and paste a chunk of html code and update links every week.

<script>
	$(function(){
		$("#header").load("header.html"); 
	});
</script>

Readings:

1. Shaffer, Clifford A. et al. Algorithm Visualization: The State of the Field. ACM Transactions on Computing Education (TOCE) 10.3 (2010)

This paper aims to provide an overview of the state of the field of algorithm visualization. The authors created a Wiki called AlgoViz and introduced common AV projects. They also collected the data of AV counts by topic. As a result, they find that a great majority of AV projects are about sorting algorithms, with only around 2% focusing on NP-Completeness algorithms and a small amount about compression algorithms. This unequal distribution across topics is quite worrying. The authors also point out that high-quality AVs are among a greater number of low-quality AVs, making it hard for instructors to find an effective AV for class.

2. Pillay, Nelishia. Learning Difficulties Experienced by Students in a Course on Formal Languages and Automata Theory. ACM SIGCSE Bulletin, 41.4 (2009) 48-52

This paper describes the result of a study on difficulties students experience when learning about formal languages and automata theory (FLAT). Students generally find that using visualization softwares such as JFLAP very helpful. However, they still face various kinds of challenges. For regular languages, when minimizing states in a DFA, some students combine two final states together when they are not indistinguashable. When converting NFA to a regular expression, a number of students forget that multiple simple paths can be between two nodes. Two difficulties described above are just examples from this paper. The author hopes to help with education of FLAT courses by identifying these difficulties.

3. Naps, Thomas et al. Development of XML-based Tools to Support User Interaction with Algorithm Visualization. ACM SIGCSE Bulletin 37.4 (2005) 123-138

The authors point out that AV is effective only when combined with a certain level of interaction. These interactions include viewing, resonding, changing, constructing and presenting, from minimum interaction to maximum. The methods to achieve these interactions include graphical primitives to visualize, hypertext documents, interactive questions and input generators. As there will be many softwares implementing these functions. The authors propose that a standard XML language be constructed to ensure portability across different AV systems. In this way the efficiency of the field of AV development will be greatly improved.

Day #3 on JFLAP

Today I read chapter 4 of Linz’s book. This chapter is about properties of regular languages and how to identify nonregular languages. I find the Pumping Lemma especially useful in differentiating nonregular languages from regular ones. I also realize that definitions and preconditions need to made crystal clear when using these kinds of theorems.

I then read the source code of FA.js and serializableGraph.js written by Sung-hoon and Martin last summer. There is no available documentation so I had to go through each of the functions to see what it does. They did an amazing job with the finite automaton class and I think all the functions I would need are already provided by them. Comments are nice too. With this new experience I improved the demo using their class. I am still having a little trouble understanding how FAEditor is implemented, but I should be able to figure it out in the next few days.

I also read the thesis by Ian. Formal reference and summary are below:

 

McMahon, I. C. Improving the Capabilities of JFLAP: Creating Effective User Interfaces in Learning for Theoretical Computer Science. Retrieved fromhttps://users.cs.duke.edu/~rodger/ianThesis.pdf

Ian first established that automata and formal languages theory are very important topics in computer science. Then he introduced the software JFLAP. JFLAP through over 20 years of development, is a mature software with widespread use. The author comprehensively improved the functionalities of JFLAP 7.0, such as boosting the user interface experience, adding useful buttons and inner structure improvement. This thesis tells me that user experience as important as functionalities in software development, and I will remember that during the development of online version of JFLAP.

 

I also read a little documentation of underscore.js. I realize that it can be used to simplify code in JFLAP development. It is heavily used in FA.js so it is essential to understand it.

Day #2 on JFLAP

Here’s the blog post I wrote for day 2 on JFLAP.

Today I read sections 3.2 and 3.3 of the Linz book. I understand the relationship between regular expression, regular language and regular grammar. I now know that they can be transformed to one another. I still not quite understand the proof for Theorem 3.5, specifically about the part where the author mentions the reverse of regular language. I did some more exercises relative to the material. Besides learning about the theories, I also learned more about JFLAP software usage. By following the tutorial on JFLAP tutorial, I now know how to transform NFA to DFA, minimize DFA and also transforming DFA to regular grammar and regular expressions.

I then read the independent study thesis written by James Cho last summer. Formal reference and summary are below:

 

Cho, James. Integrating JFLAP into OpenDSA. Retrieved from http://people.duke.edu/~sc316/jcho_paper.pdf.

In this paper, the author first established that algorithm visualization (AV) is tremendously helpful for data structure and algorithm (DSA) education. However, instructors find it time-consuming to integrate AV into their lectures. Therefore, some pioneer professors found the project OpenDSA which aims to create DSA educational softwares for computer science classes. There have also been other projects such as JHAVE and JFLAP, but they both require the installation of Java, which sometimes cause security and software compatibility problems. Due to such need, the author tried to integrate JFLAP into OpenDSA project to help with DSA education.

The project depends heavily on JSAV, an open-source JavaScript Library that supports the creation of algorithm visualizations. This allows JFLAP to be rewritten in html/css and JavaScript, which ideally makes it compatible to all devices and browsers. The author first created a prototype of DFA machine in Java and then rewrote the program in JavaScript with the help of JSAV API and Raphael library (a drawing library). As a result, the demo is able to let users follow how a string is processed in a DFA and view the result of acception or rejection.

 

This project indeed helps with OpenDSA development, but limitations abound. The most worrying limitation would be that the exercise is fully hardcoded, which makes it completely unable to provide a different DFA machine. Although part of JFLAP function is moved to web version, the project is still unable to support mobile devices for now, which was one of the main goals of the project. There are also some graphical limitations. During my internship this summer, I hope to overcome these challenges.

I then read the documentation for JSAV and also code written by Sung-hoon Kim last summer. Then I built this small demo as practice. I notice that Sung-hoon is using the function jsav.ds.fa to instantiate a graph. However I did not find that in the documentation and used jsav.ds.graph instead. One challenge that I encountered was nodes collapsed onto one another. This was resolved by calling graph.layout();. The simple demo can toggle highlight after mouseclick.

The demo that I built today is located on the very server that I am using WordPress, just under a different directory.

First day on JFLAP project

Today is my first day working on JFLAP project! JFLAP is an educational software that teaches students about automata and turing machines etc. As instructed by my supervisor, I created a blog here. I’m just going to copy and paste what I write there to here daily.

Here’s my first day blog:

Today is my first day of working on JFLAP, and I actually did quite a lot. I got two books in the morning: Formal Languages and Automata by Linz and JFLAP by Rodger and Finley. I finished reading the first two chapters of Linz’s book. The first chapter introduces some basic concepts that include language, grammer and automaton, while the second teaches me about deterministic finite automata (DFA) and nondeterministic finate automata (NFA). I learned that these two automata may seem different, but they are able to transform to one another.

I then downloaded version 7 of JFLAP and tested the software following the JFLAP intro book. The software is very easy to use and since I read the chapters in Linz’s book, the graphs were familiar to me. I find that there are also many other features besides DFA and NFA. Hope that I can learn about them later in the summer.

In the afternoon I was given access to a cs.duke.edu server. To my frustration my account is not a sudoer, which means for now I can only build this blog with html and css. I will see if I can install wordpress later. That will make this website much prettier. In either case there will be many changes to this page for sure.

A lot left to learn, wish myself best of luck.