Masaryk University
Faculty of Informatics
Web Editor of Finite Automata
Bachelor’s Thesis
Patrícia Salajová
Brno, Spring 2021
Masaryk University
Faculty of Informatics
Web Editor of Finite Automata
Bachelor’s Thesis
Patrícia Salajová
Brno, Spring 2021
This is where a copy of the official signed thesis assignment and a copy of the Statement of an Author is located in the printed version of the document.
Declaration
Hereby I declare that this paper is my original authorial work, which I have worked out on my own. All sources, references, and literature used or excerpted during elaboration of this work are properly cited and listed in complete reference to the due source.
Patrícia Salajová
Advisor:doc. RNDr. Jan Strejček, Ph.D.
Acknowledgements
I want to express my gratitude to my advisor doc. RNDr. Jan Strejček, Ph.D., as well as to my consultant RNDr. Vladimír Štill, Ph.D., for all their insightful advice, frequent consultations about design choices during the implementation of the editor, and assistance with any issues that have arisen.
I also want to thank my family and all my friends for their support during my studies.
Abstract
The aim of this thesis is to implement an editor for describing finite automata, regular grammars and regular expressions, which can be inserted into ROPOT applications of IS MU. The editor allows users to create finite automata in transition diagram and transition table representations and converts them into a textual representation in the syntax of the evaluation service. The thesis provides the necessary theoretical background, a high-level description of the editor, and discusses used technologies and essential parts of the implementation.
As a part of the thesis, a script for inserting the editor into ROPOT applications was also created.
iv
Keywords
formal languages, finite automata, web application, e-learning, JavaScript, ROPOT
Contents
1 Introduction 1
2 Preliminaries 3
2.1 Languages and their finite representations . . . 3
2.1.1 Grammars . . . 4
2.1.2 Chomsky hierarchy of grammars . . . 5
2.1.3 Regular expressions . . . 6
2.1.4 Finite automata . . . 7
2.1.5 Finite automata representations . . . 10
2.2 Syntax of the evaluation service . . . 11
2.2.1 Finite automata . . . 11
2.2.2 Regular grammars . . . 13
2.2.3 Regular expressions . . . 14
3 Editor usage 17 3.1 Editor for automata . . . 17
3.1.1 Graph . . . 17
3.1.2 Table . . . 23
3.1.3 Text . . . 26
3.2 Editor for regular grammars and expressions . . . 27
4 Implementation 29 4.1 Editor . . . 29
4.1.1 JavaScript libraries . . . 30
4.1.2 Other prerequisites . . . 32
4.1.3 Directory structure . . . 32
4.1.4 Important objects and classes . . . 33
4.2 Integration into IS . . . 34
4.2.1 Script for converting question sets . . . 37
5 Conclusion 39
Bibliography 41
A Example question sets 43
B Appendices in IS MU 45
viii
List of Figures
2.1 Schema of a finite automaton 7 2.2 Transition table for a DFA 10 2.3 Transition diagram for an EFA 11 2.4 Transition diagram for a DFA 13
3.1 Editor in the graph mode with syntax rules shown 18 3.2 Editor in the graph mode with a state context menu opened 20 3.3 Editor in the graph mode with an error 21
3.4 Editor in the table mode 23
3.5 Editor in the table mode with a syntax error 25 3.6 Editor in the text mode 27
3.7 A regular grammar with correct syntax 28 3.8 A regular expression with incorrect syntax 28 4.1 Class diagram of the editor 33
A.1 Example of a question set 43
A.2 Question set after the insertion of the editor 44
1 Introduction
Formal languages and automata are an integral part of computer sci- ence and have been taught at the Faculty of Informatics of Masaryk University since its foundation. In the course IB005Formal Languages and Automata, students learn, among other things, about finite au- tomata, regular grammars, and regular expressions. The IB005 course utilises several ROPOT1applications (ROPOTs) as part of the home- work set and also as optional practice. It is advantageous that ROPOTs can be evaluated automatically by an external service, therefore they do not have to be checked manually by teachers. Additionally, students have the results available immediately, without the risk of human error, and can work with ROPOTs repeatedly. However, to define an automa- ton in the syntax used by the evaluation service can be unintuitive and time-consuming.
To combat this drawback and make working with ROPOTs more convenient for students, three different editors were made in the re- cent years by students of the Faculty of Informatics as their bachelor’s theses. The first was authored by Michaela Bukovenová in 2014 [1], the second by Matúš Šmýkala in 2015 [2]. Both were Java applets.
At that time, to run an applet, users had to install and enable a Java plug-in in the browser, and mobile browsers were not capable of run- ning Java applets at all. Today, Java applets are an outdated technology that is no longer supported by browsers. In 2016, Matej Poklemba cre- ated the latest editor [3] which, unlike the two older editors, was writ- ten in JavaScript and as such was supported in all the major browsers and required no additional installations.
Even though Matej Poklemba’s editor was serving its purpose well, the main goal of this thesis is to replace it with a new one. There were several reasons for this, mainly to make the editor compatible with the new design of the Information System of Masaryk University (IS MU). In addition, the new editor should be more ergonomic, more intuitive to use and it should also support localisation.
The rest of thesis is structured into four chapters. In the second chapter we introduce basic theoretical definitions and terms concern- ing finite automata, regular expressions and grammars. We also de-
1. acronym standing forRevisionOpinionPoll andTesting
1. Introduction
scribe the syntax of the evaluation service used for ROPOT applica- tions in IB005. The third chapter contains a high-level description of the editor’s functionality. The fourth chapter is dedicated to the imple- mentation of the editor and used technologies. We also describe the process of integration of the editor into ROPOT applications. Lastly, the final chapter concludes with a discussion about feedback from students, possible editor improvements and follow-ups.
As the outcome of this thesis, a fully functional editor was created and integrated into IS MU. The source code of the editor is accessible via a public GitHub repository2.
2. available athttps://github.com/psalajova/ISMU-AutomataEditorD3
2
2 Preliminaries
In this chapter we aim to provide the theoretical background for the editor. In the first section, we define all the necessary knowledge of the theory of formal languages relevant to this thesis.
As the main goal of this thesis was to create an editor that can be integrated into ROPOT applications, it is also important to describe the syntax of the service that evaluates the answers for the ROPOTs’
questions. We summarize this syntax in the second section.
2.1 Languages and their finite representations
This section provides basic definitions concerning regular languages, finite automata, regular grammars, and regular expressions. If not stated otherwise, all definitions have been taken from the official IB005 textbook [4].
Definition 2.1.1. Analphabetis any finite set Σ, the elements of which are calledsymbols(alsoletters,characters) of the alphabet.
Definition 2.1.2. A string (or a word) v over an alphabet Σ is any finite sequence of symbols from Σ. The number of elements in the sequencevis called thelength of a string v, and its standard notation is
|v|. A sequence with zero elements is called theempty string, denoted byε, which length is zero.
Definition 2.1.3. We denote the set of all strings over an alphabetΣ byΣ∗ and the set of all nonempty words byΣ+. A languageLoverΣ is any subset of strings overΣ(languages overΣare subsets ofΣ*).
Not all languages are finite, as a language may contain an infi- nite number of words. The problem of how to finitely represent such languages arises. Even if a language is finite, a simple listing of all the words can be inefficient if the number of words is extensive. It is important to note that a finite representation does not exist for every language.
In the following sections, we describe those representations of for- mal languages which are applicable for this thesis.
2. Preliminaries 2.1.1 Grammars
Definition 2.1.4. AgrammarG is a quadruple (N,Σ,P,S), where
• Nis a nonempty finite set ofnonterminal symbols(nonterminals),
• Σis a finite set ofterminal symbols(terminals) such thatN∩Σ=
∅; the union of N andΣresults in a set V of all symbols of the grammar,
• P⊆V∗NV∗×V∗is a finite set ofrules(also calledproductions),
• S ∈ Nis a special nonterminal called thestart symbolor theroot of the grammar.
A rule (α,β) is usually written asα →βand read as “αrewrites to β”. The condition imposed on the form of rulesα → βdemands only thatα(called theleft side of a rule) contains at least one nonterminal.
Generally, no requirements are placed on β(theright sideof a rule).
In particular, it can also be an empty wordε.
Given a grammarG = (N,Σ,P,S), the binary relation⇒G called aderivation in one stepis defined as follows. Letη,ρ∈ V∗be sequences of symbols and(α → β) ∈ Pbe a rule. We writeγ ⇒G δifγ = ηαρ andδ =η βρ. IfGis understood from the context, we may writeα ⇒β instead ofα ⇒G β[5].
We also introduce the relationderivation⇒∗G, which is the reflexive transitive closure of⇒G.
All elements ofV∗that can be derived in a finite number of steps from the start symbol of a considered grammar are calledsentential forms. A sentential form that does not contain any nonterminals is called a sentence. The set of all sentences creates the language of G, denotedL(G)[6]:
L(G) = {w∈ Σ∗ | S⇒∗G w}
There are several standard conventions we will adhere to in this text:
• Rules α → β,α → γ with the same left side can be shortened intoα →β| γ.
4
2. Preliminaries
• Terminals are written in lowercase Latin letters from the start of the alphabet.
• Nonterminals are written in uppercase Latin letters from the start of the alphabet.
• Sequences composed solely of terminals are written as lowercase Latin letters from the end of the alphabet.
• Sequences fromV∗are usually written as small Greek letters.
2.1.2 Chomsky hierarchy of grammars
The linguist Noam Chomsky divided grammars into four categories (types) based on various restrictions on the shape of the grammar rules.
type 0 Any grammar is a type 0 grammar, the shape of rules is not restricted in any way. These grammars are also known asphrase grammars.
type 1A grammar is a type 1 grammar (alsocontextgrammar or context-sensitive, CSG) if each ruleα→ βsatisfies a condition|α| ≤ |β|. An eventual exception of the ruleS →εis allowed ifSdoes not appear on the right side of any rule.
type 2A grammar is a type 2 grammar (alsocontext-free, CFG) if each rule is in the formA →α, where|α| ≥1. An eventual exception of the rule S → ε is allowed ifS does not appear on the right side of any rule.
type 3A grammar is a type 3 grammar (alsoregulargrammar or right-regular) if each rule is in the formA →aBorA→ a. An eventual exception of the ruleS →εis allowed ifSdoes not appear on the right side of any rule.
Chomsky grammar hierarchy also determines the corresponding language hierarchy. A language L is regular (or context-free,context- sensitive, recursively enumerable, resp.) if a regular (or context-free, context-sensitive, phrase, resp.) grammarGexists that satisfiesL(G) = L.
2. Preliminaries
2.1.3 Regular expressions
Definition 2.1.5. The set of regular expressions over an alphabet Σ, denotedRE(Σ), is inductively defined as follows.
1. ε,∅ and a for each a ∈ Σ are regular expressions overΣ (so- calledatomicregular expressions).
2. IfE,Fare regular expressions overΣ, then(E.F), (E + F)and(E∗) are also regular expressions overΣ.
3. Every regular expression is constructed by a finite number of ap- plications of steps 1–2.
Regular expressions contain parentheses as metasymbols which help define the range of operators. To minimise their usage, we adopt a convention concerning the priority of the operators: iteration “*”
has the highest priority, thenconcatenation“.”, and lastly “+” (which equates to union of two regular expressions). All redundant paren- theses can be omitted. Expressiona+b.c∗equates to expression(a+ (b.(c∗))). Unlike regular grammars, regular expressions do not contain any form of recursion.
Every regular expressionEover an alphabetΣdescribes(precisely determines) a language L(E)over the alphabetΣ(a languageL(E)is thesemanticsof a regular expressionE) according to these rules:
L(ε)def= {ε} L(∅)def= ∅
L(a)def= {a}for eacha∈ Σ L(E.F)def= L(E).L(F)
L(E+F)def= L(E)∪L(F) L(E∗)def= L(E)∗
In conclusion, a language overΣisregularif and only if it can be described by some regular expression overΣ.
6
2. Preliminaries 2.1.4 Finite automata
There are many systems whose behaviour can be described using a finite amount of states and transitions among those states. We call these systems finite-state transition systems. There are many real- life examples of such systems: a vending machine, elevators, a game of chess, even classic computers. To represent finite-state transition systems, we use an abstract model calleda finite automaton[7].
A finite automatonis equipped with a finite control represented by states and transition function, a reading head, and a tape on which the input word is written (see Figure 2.1 for illustration). At any speci- fied moment, the finite control is in one of its states. The tape is divided into cells, one next to the other.
At the beginning of computation, the reading head is placed at the leftmost cell of the tape and the finite control is in its distinguished initial state. The automaton reads an input symbol, and according to its current state and transition function, it changes the state and moves the reading head by exactly one cell to the right. The computation ends when the automaton halts the computation or if the whole input word has been read.
The automatonaccepts the word written on the tape if it is com- pletely read and the resulting state is one of the predeterminedfinal states. The set of all words that are accepted by a given finite automaton Mcreates the language L(M)accepted by the automatonM.
Figure 2.1: Schema of a finite automaton
2. Preliminaries
Definition 2.1.6. Afinite automatonis a five-tupleM = (Q,Σ,δ,s,F), where
• Qis a finite set called thestates,
• Σis a finite set called theinput alphabet,
• δ : Q×Σ →Qis a partialtransition function,
• s ∈ Qis theinitial state, and
• F⊆Qis the set ofacceptingorfinal states.
To define the language accepted by a finite automaton, we must first define theextendedtransition functionδˆ: Q×Σ∗ →Qinductively according to the length of a word fromΣ∗:
δˆ(q,ε) =q for each stateq ∈ Q δˆ(q,wa) =
δ(δˆ(q,w),a) ifδˆ(q,w)andδ(δˆ(q,w),a)are defined,
⊥ otherwise.
The symbol⊥means that the function is not defined. Intuitively, δˆ(q,w) = psays that the automatonM makes a series of transitions from the state q “under the word” w (i.e., by successively reading the word wcharacter by character, from left to right) to the state p.
The language acceptedby a finite automaton M, denoted L(M), is the set of those words under which the automatonMmakes a series of transitions leading from the initial state to some final state:
L(M) ={w ∈Σ∗ | δˆ(s,w) ∈ F}
Finite automataMandM0are language equivalent if they accept the same language – i.e., if L(M) = L(M0).
In the following text we refer to a finite automaton from Definition 2.1.6 as adeterministicfinite automaton, abbreviated as DFA.
A complete DFA For each DFA M exists an equivalent DFA M0 with acomplete transition function, meaning a transition for each state and each input symbol is defined.
8
2. Preliminaries A minimal DFA A complete DFA M is minimalfor the language L(M)if there exists no other complete DFA which accepts the same language and has less amount of states.
A canonical DFA A minimal DFA M for the language L(M) is unique, except possibly for state names. Acanonicalform of a DFA is a standard representation which lies in renaming the states of a DFA in a specific way. If two deterministic finite automata accept the same language, then they will have the same canonical form.
Nondeterminism During a computation of a DFA, its next state is uniquely determined by its current state and the input symbol. How- ever, finite automata can also accommodate the a concept ofnonde- terminism. It is a generalization of determinism which says that in a nondeterministic machine, several choices may exist for its next state at any point [6]. In other words, such an automaton can “choose” from a set of possible next states. An input wordwof such automaton is accepted if at least one of all possible computations overwends in a final state.
Definition 2.1.7. Anondeterministic finite automaton(NFA) can be de- scribed by a five-tupleM= (Q,Σ,δ,s,F)where all elements remain the same as in Definition 2.1.6, with the exception of the transition function which is defined as a total functionδ: Q×Σ→2Q.
The model of nondeterministic finite automaton can be further extended with the so-called ε-transitions. Such automaton is called nondeterministic finite automaton withε-transitions.
Definition 2.1.8. We formally describenondeterministic finite automata withε-transitionsby defining the transition function as:δ : Q×(Σ∪ {ε}) →2Q (note thatεis not a member ofΣ).
Effectively, this means that the automaton is allowed to make a tran- sition to another state without reading any input symbol. In the fol- lowing text we will refer to a nondeterministic finite automaton with ε-transitions as an EFA.
Both NFA and EFA are extensions of the finite automaton model and they describe the same class of languages as DFA.
2. Preliminaries
2.1.5 Finite automata representations
The specification of a finite automaton as a five-tuple with a detailed description of the functionδcan be tedious and hard to read. There are two alternative and often preferred representations: the transition table and the transition diagram.
Atransition tableis a tabular listing of the functionδ. The row head- ers represent states, the column headers represent the input symbols, and the results of the transition function are contained in the inner cells of the table. If the transition function is not defined for a pair of a state and an input symbol, the corresponding cell contains the symbol “-”. Entries in the table of a nondeterministic finite automaton are sets, and if a state has no transition on a given input, the entry is∅.
The initial state is marked with the symbol “→” and the final states with the symbol “←”. Figure 2.2 shows a transition table for a DFA.
Figure 2.2: Transition table for a DFA
Transition diagramsare the most intuitive and often the most con- venient way to represent automata. A finite automaton is portrayed as a directed graph in which states are the nodes and transitions are the edges labeled with input symbols. The final states are marked with double circles and the initial state is marked with the symbol “→” without a label. Figure 2.3 shows a transition diagram for an EFA.
10
2. Preliminaries
q0
q1
q2
q3 q4
ε
ε
b b a
a
c
a,b
Figure 2.3: Transition diagram for an EFA
2.2 Syntax of the evaluation service
The course IB005 utilises multiple ROPOT applications, as practical training is important to fully grasp the subject. The aim of this thesis is to implement an editor which can be inserted into ROPOTs and make working with them more comfortable. The questions in ROPOTs can be of multiple predefined types1and the editor can be a part of those questions whose type is “e”, meaning they are evaluated by an external web service. The service requires the answers to be written in a specific syntax, with its full description available at https://fja.fi.muni.
cz/reg/about. In this section, the syntax for finite automata, regular grammars and regular expressions is described.
2.2.1 Finite automata
The syntax of the evaluation service for a finite automaton consists of three parts: the initial state, the transition function, and the final states.
These three parts must be in the following order (any other order will cause a parsing error):
1. Theinitial stateis defined asinit=s1, wheres1is a state name.
2. Thetransition functionis composed of transitions defined as fol- lows (s1,s2are state names andais an input symbol):
• for DFA:(s1,a)=s2
• for NFA and EFA:(s1,a)={s1,s2}
1. https://is.muni.cz/napoveda/elearning/typy_otazek
2. Preliminaries
In case of EFA, a transition under the empty word can be written usingεor\ein place of the input symbol, e.g.,(s1,\e)={s2}or (s1,ε)={s2}.
3. The set offinal statesis defined asfinal={s1,s3}, wheres1,s3 are state names. It has to be divided from the transition function by at least one white-space character (e.g., a space or a new line).
If the automaton has no final states, this part cannot be omitted, and has to be written asfinal={}.
Between these three parts, as well as between individual transitions, any number of white-space characters can appear. Theinit=s1part may be omitted and in such case the first state found in the transition function is identified as the initial state.
A state name or a symbol of the input alphabet can be:
• a nonempty sequence of lowercase and uppercase letters of the English alphabet, numbers, or symbols “_” and “´”,
• a nonempty sequence of any characters, except quotation marks and white-space characters, enclosed in quotation marks, e.g.,
"ABCD1" or "a@$!".
The symbolsεand\eare reserved for the empty word and can- not be a part of a state name or another input symbol. Additionally, the wordsinitandfinalare reserved as key words of the evaluation service and they cannot be used as state names or input symbols.
In case a transition from a state under the same input symbol is present more than once (e.g.,(s1,a)=s1 (s1,a)=s2), the evaluation service will take into consideration only the last such transition. How- ever, doing so is not recommended and will cause a warning from the evaluation service.
Definition 2.1.6 of an automaton as five-tuple allows to include sym- bols in the input alphabet under which no transition exists. In contrast, the input alphabet of an automaton specified in the syntax of the eval- uation service is composed precisely of those symbols under which there exists at least one transition. Analogously, this distinction applies toQ(the set of states).
The DFA depicted in Figure 2.4 could be written in the syntax of the evaluation service asinit=q0 (q0,a)=q1 (q0,b)=q1 (q1,a)=q1 (q1,b)=q1 (q1,c)=q0 final={q1}.
12
2. Preliminaries
q0 q1
a,b
c
a,b
Figure 2.4: Transition diagram for a DFA 2.2.2 Regular grammars
To define a regular grammar in the syntax of the evaluation service, it is sufficient to write only its set of rules. The first found nonterminal is identified as the start symbol.
In the syntax of the evaluation service, anonterminalis one of the following:
• a uppercase letter of the English alphabet, e.g.,AorB
• a nonempty sequence of lowercase or uppercase letters of the En- glish alphabet, numbers, or the symbol “_”, enclosed in chevrons, e.g.,<aBA>or<A_2>,
• one lowercase letter of the English alphabet or any of the previ- ous cases (a uppercase letter or a sequence in chevrons) followed by one or more apostrophes, e.g.,S’,<S_0>’orA’’
A terminal is either a lowercase letter of the English alphabet, a number, one of the symbols “~”, “=”, “-”, or a sequence of any symbols, except quotation marks and white-space characters, enclosed in quotation marks, e.g.,"abcd". The empty word is written asεor\e.
A regular grammar is accepted if all its rules are in one of the following forms (A,B,Sare nonterminals anda,bare terminals):
• A -> bB,
• A -> a,
• S -> \e, ifSis the start symbol and is not on the right side of any rule.
2. Preliminaries
The arrow between the left and the right side of a rule can be written either as->or as the Unicode symbol →. Rules with the same left sides can be shortened using the symbol “|”, e.g., A->aA | bB | a. Apart from names of terminals and nonterminals, spaces and tabs can be written anywhere, however, a new line always separates rules.
Rules for individual nonterminals have to be separated by a comma, the symbol “;” or by a new line.
A regular grammar written in the syntax of the evaluation service could be, for example,
S -> dD’ | aA | ε A -> dD’ | a D’ -> aA | d
orS -> a<ab> | b<BB>; <ab> -> b<BB>| a; <BB> -> a<ab>. 2.2.3 Regular expressions
All operators and symbols have the same meaning as in the Defini- tion 2.1.5. The syntax of theatomic regular expressionsis as follows:
• the empty word can be written as\eorε,
• the empty set as\0or∅,
• a symbol of the input alphabet can be any lowercase or uppercase letter of the English alphabet, a number (e.g.,a,Ror9), or a se- quence of any characters, except quotation marks or white-space characters, enclosed in quotation marks, e.g.,"Xy0&!".
The priority of operators is the same as in Definition 2.1.5, meaning iteration has the highest priority, then concatenation, and lastly the “+”
operator. The syntax of these operators is as follows:
• iteration is written asˆ∗ and positive iteration2 asˆ+, e.g.,aˆ∗ or aˆ+ (the iteration is applied to the character or the regular expression in parenthesis on the left side of the operator),
2. Here, thepositive iterationoperator is used to simplify writing of the iteration of a regular expression one or more times, e.g.,aˆ+is equal toa.(aˆ*).
14
2. Preliminaries
• concatenation is written as the dot symbol “.” between two reg- ular expressions, e.g.,a.b,
• the operator “+” is written as+between two regular expressions, e.g.,a+b.
Regular expressions can be enclosed in parentheses, e.g.,(a.b). Writing multiple symbols of the input alphabet immediately after each other is evaluated as their concatenation (ab is equivalent to a.b). This applies not only to the symbols of the input alphabet, but also to iterated regular expressions and regular expressions enclosed in parentheses (abcˆ∗a(b+c)is equivalent toa.b.((c)ˆ∗).a.(b+c)).
All white-space characters are ignored and do not affect the evaluation.
In the following list we provide several examples of regular expres- sions written in the syntax of the evaluation service:
• abˆ∗ is equivalent toa.((b)ˆ∗)
• (a + b + cˆ∗) + \eis equivalent toa+b+(c)ˆ∗+ε
3 Editor usage
This chapter showcases the behaviour of the editor from the user’s point of view. Similarly to its predecessors, the primary purpose of this editor is to make the description of finite automata easier and more comfortable, as regular grammars and regular expressions can be relatively simply represented as text in the syntax of the evaluation service. Accordingly, the editor’s functionality for the description of fi- nite automata is much more advanced than it is for regular grammars and expressions.
3.1 Editor for automata
Users can work with the editor in three modes that correspond with finite automata representations mentioned in Chapter 2:
• thegraph mode– the transition diagram,
• thetable mode– the transition table,
• thetext mode– according to the syntax of the evaluation service.
The user can switch between these three modes at any moment using the menu buttons at the top of the editor, which are appropriately labeledGRAPH,TABLE, andTEXT.
3.1.1 Graph
TheHINTbutton lies directly below menu buttons. Upon clicking, it can show or hide a text box containing basic instructions for users about creating and manipulating elements of the automaton.
Similarly, the SYNTAX button positioned next to the HINTbutton shows and hides a text box holding basic syntax rules under which the editor operates. A state name can be any string of characters of low- ercase and uppercase letters of the English alphabet and numbers.
A transition can be labeled with a lowercase or uppercase letter of the English alphabet, a digit, or a sequence of any symbols, except quota- tion marks and white-space characters, enclosed in quotation marks.
3. Editor usage
If the automaton is an EFA, a transition can also be labeled with ε or \e. Transitions that differ only in input symbols are represented by one edge labelled with the list of these symbols (e.g., a,b,c, or
“dog”,“cat”,“mouse”).
The maincanvas(or work-space), where an automaton can be cre- ated, lies below these two buttons. The editor’s visual representation (see Figure 3.1) of the automaton is based on the transition diagram:
1. statesare depicted as circles with their names in the middle, 2. theinitial stateis the state with an unlabeled arrow pointing to
it,
3. final statesare portrayed as double circles,
4. transitionsare depicted as directed edges between source and target states, labeled in the middle with the list of input symbols.
Figure 3.1: Editor in the graph mode with syntax rules shown 18
3. Editor usage When the editor is first loaded, the graph representation is selected by default. To indicate that the canvas is empty (it contains no states), it is inthe empty state– the background is greyed out and a message about its empty status is shown. After the first state is created, this state is ended and the message disappears. The editor returns to the empty state every time a user deletes all transitions and states. In an active ROPOT session, this behaviour helps to indicate that a question has been unanswered so far.
There are two ways tocreate a new state:
1. by double-clicking on the canvas,
2. by right-clicking on the canvas and selecting the option to create a new state from the context menu.
A new state is created in the position where the user’s mouse was pointing and is automatically assigned a unique name. This name is composed of the letter “s” followed by the first unused number in ascending order (e.g., “s1”, then “s2” and so on).
Right-clickingon a state will open a context menu (as shown in Figure 3.2) with the following actions offered to the user:
• rename– initialises renaming of the state
• delete– deletes the state and all adjacent transitions
• make accepting / make non-accepting– if the state was accepting, it is set as non-accepting and vice versa
• make initial– sets the state as initial; this option appears only if the state is currently not initial
Renaming a state The user can rename a state by right-clicking on the state and choosing therename option in the context menu or by double-clicking on the state’s name. During renaming, the dragging of all elements on the canvas is disabled.
The renaming can be finished by pressing ENTER. If the newly typed name is invalid (e.g., it violates the syntax rules or a state with
3. Editor usage
Figure 3.2: Editor in the graph mode with a state context menu opened that name already exists), an error message will pop up with an ap- propriate message saying what went wrong. Renaming can also be ended by clicking anywhere on the canvas or by pressing the ESCAPE key. However, in those cases, the error message will not pop up. If the new name was valid, the state is renamed. Otherwise, the state’s name is reverted to its previous value.
Anew transitioncan be created by following these steps:
1. Click on a state; an edge coming out of this state will appear, indicating where the transition will be placed.
2. Click on another state (or the same state to create a self-loop).
3. An input dialog will appear into which the input symbols can be typed. In case the automaton is an EFA, the default input value will beε, otherwise it will be empty.
4. Finish by pressing ENTER, ESCAPE, or clicking on the canvas.
20
3. Editor usage Right-clickingon an existing transition will open a context menu with the following actions offered to the user:
• edit transition symbols– initialises editing of the transition’s input symbols,
• delete– deletes the transition.
Editing transition’s symbols The initialisation of editing of transi- tion’s input symbols is analogous to renaming of a state – it can be done by double-clicking on the rectangle housing the transition’s in- put symbols or by right-clicking on a transition and choosing theedit transition symbolsoption. After typing the desired symbols, editing can be finished by pressing ENTER, ESCAPE or clicking anywhere on the canvas. If the transition is invalid, an appropriate error message will pop up, as shown in the following figure:
Figure 3.3: Editor in the graph mode with an error
3. Editor usage
The only difference from renaming a state is if a transition is newly created and its symbols are not valid; by clicking on the canvas or pressing the ESCAPE key, the transition will be deleted. This is because the transition is new and therefore has no previous valid symbols to revert to.
To keep the graph easy to read, when a user tries to create a new transition between two states and a transition already exists between these two states, rather than to create an entirely new edge, the editor automatically initialises the editing of the existing transition’s input symbols.
Dragging Both states and transitions can be dragged (moved around the canvas). When dragging a state, it changes its position according to where the user is pointing. The dragging of a transition bends it, or – in case of a self-loop – rotates it around its source state.
Dragging or clicking on an element (a state or a transition) also selectsthe element. Only one element can be selected at a time, as the selection of multiple elements is currently not supported.
Pressing the DELETE key deletes the currently selected element.
When a state is deleted, all transitions leading from and to this state are deleted as well.
To preserve consistency when multiple editors are on one web page, only one of the editors can be active at a time. This means only one state or edge can be selected and interacted with at a time (e.g., if a user selects a state in editor A and then manipulates some part of an editor B, the state in editor A will be deselected).
Zooming & panning The canvas can be zoomed in and zoomed out using mouse wheel scroll or other commonly supported gestures (e.g., sliding or pinching the touchpad). Zooming is allowed within predetermined limits; the canvas size is not infinite but is sufficiently large to fit most automata. The editor also supportspanning– users can hold and drag the canvas to bring another part of the canvas into focus.
22
3. Editor usage 3.1.2 Table
As the second mode of the editor, the table mode is often preferable when the task is, for example, to convert an EFA into an equivalent DFA, in accordance with the way the algorithm is taught in the course IB005.
A SYNTAX button is situated above the table and, as well as in the graph mode, it contains syntax rules applicable to the table and its parts. The syntax rules are equivalent to the graph mode’s syntax concerning state names and transition symbols.
The table itself lies below theSYNTAXbutton. The state names are the row headers. The column headers correspond with the input sym- bols and the row/column intersections indicate the results of the tran- sition function. Figure 3.4 shows the editor for an NFA in the table mode.
Figure 3.4: Editor in the table mode
3. Editor usage
All the table cells containing state names, input symbols, and re- sults of the transition function are editable.
Adding a new state is done by clicking on the cell with the symbol
“+” located at the bottom left corner of the table. Doing so adds a new row to the table and also creates the state in the graph representation.
At the start of each row, there is a cell with the symbol “×”. This cell functions as a delete button for states; clicking on it deletes the row and all occurrences of that state in the table. This action also deletes the state from the automaton and all its incoming and outgoing transitions.
To the left of each row header containing a state name there is a cell housing two arrow symbols on top of each other. These button represent the initial and accepting status of a state. By default, both are greyed-out (deselected), which means the state is not initial and not accepting. Clicking on the top button “→” sets that state as initial, which is indicated by turning the button’s background colour to bright green. If any other state was initial before that, it will no longer be initial.
Clicking on the button “←” sets the state as accepting, which is indicated by turning its background to blue. Analogously, if it was previously selected, clicking on it deselects it and the state is no longer accepting.
Adding a new transition symbol is done by clicking on the cell with the symbol “+” in the top right corner of the table. This adds a new column to the table whose header value is set to the first lowercase letter of the English alphabet that is missing (e.g., if there are input symbolsaandc, the new column header’s value will beb).
Above each column header, there is a cell with the symbol “×”, which upon clicking deletes the column and also removes the input symbol corresponding to the column from all transitions in the au- tomaton.
The inner cells of the table represent the transition function. When the automaton is a DFA, these cells are empty by default, and each cell can contain at most one state name. In case of nondeterministic automata, each cell contains a set of state names separated by a comma, and the default value is{}, i.e., the empty set. When a user types a state name that is not present in the table, a new row with this state name is automatically added.
24
3. Editor usage Syntax checking While editing a table cell, the editor continuously checks if the cell’s value is correct. To indicate that the value is incorrect (e.g., wrong syntax or duplicate state name), the following things happen (as depicted in Figure 3.5):
1. the cell’s background becomes red,
2. all the other table cells are locked (non-editable),
3. an error message appears below the table, hinting why the cell’s value is wrong.
During the standard use of the editor, at most one cell can have an invalid value at a time. However, to address any edge case situations when two or more table cells have incorrect values simultaneously, arollback is performed – all the incorrect cells are reset to their last correct value and the table is unlocked. This is to prevent the table from locking up permanently which would cause problems while using the ROPOT application in an active session. Clicking on any of the menu buttons while the table is locked also invokes the rollback.
Figure 3.5: Editor in the table mode with a syntax error
3. Editor usage 3.1.3 Text
This editor mode displays the original text area generated automat- ically by IS after starting a ROPOT session. As it is the only part of the editor that is evaluated after submission, it is essential to note that the editor converts the automaton into the textual representation even while working in the graph or table mode and updates it after every significant change.
Text structure The text is in the syntax of the evaluation service described in Section 2.2.1 and thus only contains information about the transition function and the initial and final states. After reloading the page (e.g., after clicking “Save and continue” during a ROPOT session or when working with the same ROPOT repeatedly or brows- ing the answers after submitting), positions of states and transitions in the graph created by a user would be lost. In order to prevent this, the editor stores all the necessary data to reconstruct the graph in the textual representation, which is saved in IS as part of the answer.
In the syntax of the evaluation service, the symbol “#” marks the beginning of a commentary, which is a part of the answer that is not evaluated. Consequently, the text in the text area is divided by
“#” into two parts: the first part is the answer that will be evaluated, the second part are the position data needed to reconstruct the graph.
Figure 3.6 shows the textual representation of the automaton shown in the graph mode in Figure 3.3.
The symbol “#” is followed by the data about states. They begin with the string states and then continue with the individual state data in the following format:
@state_name;x;y
The numbers x and y are coordinates that determine the position of the state on the canvas.
The data concerning transitions are directly after, starting with the stringedgesand followed by the individual transitions in the following format:
@source_state_name;target_state_name;input_symbols;dx;dy;angle
26
3. Editor usage dxanddyare numbers used when reverse calculating the curvature of the edge,angleis a number used to calculate the angle if the edge is a self-loop. If the curve of an edge is a straight line or a self-loop has the default angle, these parts of the data can be omitted (as shown in Figure 3.6). The parts@initAngleand@tare used to recreate the angle of the arrow marking the initial state and zoom and pan level of the canvas the user left it in, respectively.
Figure 3.6: Editor in the text mode
Syntax checking The previous editors offered syntax checking func- tionality when a user was directly editing the textual representation.
In the present, the evaluation service understands the symbol “#”
as a denotation of commentary. However, the syntax checking func- tions for automata do not, and so they evaluate every text as syntacti- cally wrong, even when it is correct. We were unable to find any viable alternative solution for storing position data outside the text area or without using the symbol “#”. We decided not to directly modify the syntax checking functions and for now, syntax checking for automata is disabled and the text area is read-only.
3.2 Editor for regular grammars and expressions
In this mode, we expect the user to enter a regular grammar or a reg- ular expression in the syntax of the evaluation service (as discussed in Section 2.2) into the question’s text area.
Any changes to the text are monitored in real-time. There is a text box positioned under the text area, which reflects the current syntactic status of the text by the color of its background:
3. Editor usage
• green = correct
• yellow = so far correct but something needs to be added
• red = incorrect
At any state, the text box displays syntactic suggestions (e.g., which symbol is expected next or which symbol caused an error). Figures 3.8 and 3.7 illustrate texts with correct and incorrect syntax.
Figure 3.7: A regular grammar with correct syntax
Figure 3.8: A regular expression with incorrect syntax
28
4 Implementation
In this chapter we describe the most relevant parts of the implemen- tation of the editor, used languages and libraries. We also explain the process of integration of the editor into the ROPOT applications of the course IB005.
4.1 Editor
The editor was implemented as a web application and can be, with cor- rect initialisation, easily inserted into any web page (and consequently, into questions of a ROPOT application). The editor, similarly to its predecessor, was written inJavaScript– an object-oriented scripting programming language, which function lies in controlling the contents of a web page through handling user triggered events (e.g., when user pushes a keyboard key, clicks on a button, or types something into an input field). JavaScript is one of the three cornerstone technologies used to create web applications, alongside HTML and CSS.
HyperText Markup Language(HTML) is a descriptive language that establishes the structure of a web page [8]. An HTML document is composed of elements of various types.
To access and manipulate HTML elements, JavaScript uses theDoc- ument Object Model (DOM), which is a programming interface for HTML documents [9], implemented by all browsers. It defines the structure of documents and properties, methods and events for all HTML elements.
Cascading Style Sheets(CSS) is a stylesheet language for defining the appearance of elements of an HTML document [10]. The word
“cascading” indicates that the attributes of an element are inherited from its parents, and they can be selected based on this inheritance.
CSS enables the separation of presentation and contents of a website, improving page maintainability and keeping the source code seman- tics clear. CSS3 is the latest official version and was used to define all editor elements’ appearance.
Scalable Vector Graphics(SVG) are an XML-based markup lan- guage used to describe vector-based graphics for the Web. In compari- son with classic image formats such as PNG or JPEG, we can render
4. Implementation
images in SVG vector format in any size without any loss of quality [11].
Because of this feature, the editor uses SVG to display automaton’s components in the graph mode.
4.1.1 JavaScript libraries
The two JavaScript libraries that are the most integral in the editor’s implementation are D3 and jQuery.
D3(or D3.js) is an open-source JavaScript library for data visuali- sation and manipulation of documents created by Mike Bostock [12].
It is a widely used dynamic framework used to create interactive charts, graphs, and essentially any data structure, as it provides a large amount of functionality for making style and attribute changes to HTML elements. Because the whole D3 library consists of numer- ous modules and is quite extensive, we will mention only the basic concepts and the modules and methods that were used in the imple- mentation of the editor.
A core mechanism of D3 areselections. Selections are made using select() and selectAll()methods and are the main way to ma- nipulate the DOM through setting of attributes, properties, styles, and classes of HTML elements. With theselectAll()method, multi- ple HTML elements can be selected and transformed at once.
In the following example using theselectAll()method, we select all HTML div elements in the document. From those we select all that contain classselectorand add them a new classanother-selector:
let divs = d3.selectAll("div");
let elements = divs.selectAll(".selector");
elements.classed("another−selector", true);
Bothselect()andselectAll()methods return a selection, which allows method chaining, i.e., applications of multiple operations on the selection using the dot syntax. Therefore, the previous example can be written as:
d3.selectAll("div") .selectAll(".selector")
.classed("another−selector", true);
30
4. Implementation The top-level selection methods,select()andselectAll(), query the entire document. Thesubselectionmethods,selection.select() and selection.selectAll(), restrict the selection to descendants of the selected elements [13].
Another core mechanism of D3 isdata binding. D3 allows binding of a specified data array to a selection using thedata()method. The data()method is usually used together with theenter()andappend() methods, which are used to create any missing elements correspond- ing to the data provided. In the following example, we create four HTML paragraph elements with the matching year data binded to them:
const years = ["1995", "2001", "1887", "2020"];
d3.select("body") .selectAll("p") .data(years) .enter().append();
Theselection.datum([value])method can be used to set or get the data binded to an element.
The D3 module Drag is used to create a drag behaviour, which provides a convenient abstraction for creating drag and drop interac- tion on selections. As it processes all the relevant native web events (e.g.,mousedown,mousemoveortouchstart), it greatly simplifies event handling related to dragging gestures. In the implementation of the ed- itor it was used mainly to define state and transition dragging.
All the zooming and panning behaviour of the editor, which lets the user zoom the editor’s canvas by scrolling the mouse wheel or by pinching the touchpad, and pan the canvas to modify the view of it, was implemented using the D3 moduleZoom. Among other things, it allows restricting the extent to which the working space of the editor can be zoomed in or out, or the borders of the canvas beyond which the user is not allowed to pan.
jQueryis an open source cross-browser JavaScript library. It pro- vides an easy-to-use API for event handling and HTML document traversal and manipulation [14]. jQuery can, to a large extent, simplify programming in JavaScript. It was used to handle events and manipu- late the DOM elements, from setting attributes to modifying object classes.
4. Implementation
The JavaScript pluginjQuery UIis built on top of the jQuery library and provides multiple ways to make user interfaces more interactive.
This plugin was mainly used to make editor’s table columns resizable.
4.1.2 Other prerequisites
The syntax checking service the editor provides for regular grammars and expressions utilizes the parsing functions from the JavaScript files GRAParser.jsandREGParser.jscreated by Radim Čebiš in 2008 as his bachelor thesis [15]. The parsing functions were slightly adjusted to allow localisation.
To link the syntax parsing functions to the correct elements, we used a modified version of the functionregister()from the JavaScript fileutilIS.js, taken fromhttps://is.muni.cz/el/fi/jaro2021/IB005/
odp/support/.
4.1.3 Directory structure
The editor’s source code is accessible via a public GitHub repository available athttps://github.com/psalajova/ISMU-AutomataEditorD3. The file structure of the repository is shown in the following schema:
editor Languages
CS.js EN.js Libs
d3.v6.min.js jquery.min.js jquery-ui.min.js jquery-ui.css Parsers
DFAParser.js NFAParser.js EFAParser.js GRAParser.js REGParser.js editor.js utilIS.js
editorStyle.css Converter
convert.py 32
4. Implementation 4.1.4 Important objects and classes
The logic of the editor lies in the file editor.js, which is structured into several main classes and objects. The following simplified class diagram illustrates their relationships:
Figure 4.1: Class diagram of the editor
The classEditorModerepresents a base class for one editor mode.
The classesGraphMode,TableModeandTextModeinherit from this class, which encompass the respective editor modes and are responsible for the editor’s functionality in that mode. When a user changes from one mode to another, these classes manage the correct initialisation of their components, HTML elements, and execute any related functionality.
The GraphMode class creates all elements of the canvas, hints, and context menus. It retains all the necessary information about states, transitions, and their positions. It also contains all methods that allow users to interact with the canvas. Similarly, theTableMode class maintains elements of the table and is responsible for handling events, errors, and any other logic associated with table mode. The TextModeclass is simple in comparison, as it houses only the text area and, in case of regular grammars and expressions, provides the syntax checking functionality.
4. Implementation
The classEditoris a base class that represents an editor itself and is currently inherited by two classes:TextEditorandAutomataEditor.
Internally, the classEditor has a propertytype that can have one of the following values: “DFA”, “NFA”, “EFA”, “GRA”, or “REG”.
When the task is to create a regular grammar or a regular expression, the editor is instantiated asTextEditorwithtypeset to “GRA” or “REG”, respectively. Consequently, when the task is to create a DFA, NFA or an EFA, the editor will be an instance ofAutomataEditorwithtypeset to “DFA”, “NFA” or “EFA”, respectively.
AutomataEditor contains instances of GraphMode,TableModeand TextMode classes through which it provides all the necessary func- tionality for creating finite automata. It initialises and manages menu buttons and hints, covers interaction between modes and transitions from one mode to another.
Multiple utility classes –MathUtils,ArrayUtils,HtmlUtils,StateUtils, EdgeUtils, and EditorUtils – are also present. They group together related helper functions used by other classes.
Lastly, theEditorManageris an object that holds a collection of all editors on page, provides access to them, and also manages which of the editors is currently active, and all the necessary surrounding behaviour that is implied.
4.2 Integration into IS
To describe how we integrated the editor into ROPOT applications, we must first outline how ROPOTs of the course IB005 are structured.
A ROPOT consists of questions which are taken from one or more question sets. A question set is a text file, usually with the suffix.qdef or .qdefx, composed of questions and their answers. At the begin- ning of the file, there may be a header with additional HTML ele- ments. The start of a header is marked with two plus symbols “++”.
The header is followed by the individual questions which are divided by a new line and two dash symbols “--”.
The last line of each question in a question set is in the following format:
:e="d:?EFA−NFA:(A,b)={A,B} (B,a)={F} final={F}" ok
34
4. Implementation This line includes the type of the question, which is the type “e”.
As mentioned in Section 2.2, this means that the question’s answer is evaluated by an external web service.
The part of the string in quotation marks is the type of assign- mentof the question, based on which the evaluation service verifies the correctness of a student’s answer. The following table lists the ab- breviations (codes) that dictate the expected types of formalisms used in assignments [16]:
Code Meaning
DFA a deterministic finite automaton (DFA) TOT a complete DFA
MIN a minimal DFA CAN a canonical DFA
TOC a complete canonical DFA MIC a minimal canonical DFA
NFA a nondeterministic finite automaton
EFA a nondeterministic finite automata withε-transitions GRA a regular grammar
REG a regular expression CFG a context free grammar
The assignments are written in the formatTTT-SSS:lang, where:
• TTTis a type of formalism of the assignment,
• SSS is the expected type of the student’s answer, which also expresses any requirements for the answer (e.g., to construct a NFA or a minimal DFA),
• langis a description of a language whose type of formalism is dictated byTTTand whose language equivalence is compared with the student’s answer.
4. Implementation
For example, the assignmentEFA-NFAconveys that the task is to construct an NFA that is language equivalent to the EFA provided after the colon. Consequently, the value ofSSSdecides the value of the propertytypeof the classEditorand thus whether the editor will be instantiated asAutomataEditororTextEditor.
Embedding the editor in ROPOTs In order to insert the editor into a ROPOT, the given question sets must be accordingly modified.
Into each question set file we added a header with an HTML
<script>tag, which contains a short JavaScript code. The script im- ports all files that are necessary for the editor to function, namely editor.js,editorStyle.css, parser files, and the libraries jQuery and D3.
Additionally, we placed a<script>tag at the beginning of each ques- tion with a function calleditor_init(type), wheretypewill become the propertytypeof the classEditor.
When a ROPOT session starts, the header of each question set is loaded before their questions, importing all the necessary files. Then, as text areas for individual questions are automatically generated by IS, the function calleditor_init(type)saves a reference of that text area and the value oftypein a list. After all the text areas are generated, the functions contained in the fileeditor.jsensure that an editor with the correct value of the propertytypeis created for each text area in the list.
In the appendix A, we show an example of an unmodified question set file with three questions (see Figure A.1), and also the same ques- tion set after the insertion of the editor (see Figure A.2). The script in the header ensures that if the ROPOT is made of multiple question sets that contain editors, the files are loaded only once. The script also loads only those parser files that are necessary.
Localisation After the loading of question sets’ headers is done, but before loading the individual questions, the functionsetupLanguage() located ineditor.jsis called. Its task is to determine the current language of the page and import the corresponding language file for editors.
Language files are JavaScript files named CS.jsandEN.js, and they define all key phrases and titles that appear in an editor.
36
4. Implementation Currently, IS MU is supported in English and Czech languages, so only those two language files are included. To add another language for the editor, a new file with the translations of key words must be created.
4.2.1 Script for converting question sets
For the purpose of integrating the editor into already existing ques- tion sets, a simple script has been created. It is written in Python 3 and can be found in the directory Converter as the fileconvert.py.
It uses theos,sys,globandremodules for working with the operation system, command line arguments, files, and regular expressions.
The script can be executed from the command line as follows:
python3 convert.py <file/directory path> <extension> −s
The first argument can be either a file or a directory. If it is a file, the program checks if it has the.qdef suffix and if it does, it creates a new modified file in the current working directory. In case the ar- gument is a directory, it finds all files with the suffix.qdef it contains, modifies them and saves them in a new directory called Converted, located in the directory that was provided as the argument.
The<extension>is an optional argument, which will be appended to converted files’ names (e.g., an input file named qset.qdef with the extension_newwill becomeqset_new.qdef). If this argument is not provided, the default extension is “_new” when converting one file.
When converting a directory, no extension is added to the files’s names.
The-soption can be used when we need to convert a question set that contains parts of the previous editor. Using this option removes the old editor before inserting the new one.
During the conversion, the program gradually lists the names of the input files that are being modified, and the number of success- fully converted questions in those files.
5 Conclusion
The main goal of this thesis was to implement an editor capable of describing finite automata, regular grammars, and regular expres- sions. The editor can be inserted into ROPOT applications of IS MU and makes working with them more comfortable.
Our implementation of the editor is fully functional and compati- ble with the new design of IS MU, supports localisation, and allows to have multiple editors on one page. During an ongoing ROPOT ses- sion students can save their progress and continue where they left off. The editor is also more ergonomic and intuitive to use than its predecessors and includes a hint on how to use it.
When describing regular grammars and expressions, the editor checks their syntax in real-time using parsing functions by Radim Čebiš [15]. When describing finite automata, the user can choose between multiple representations and switch between them at any time. The editor stores states’ positions and shapes of edges as the user created them in the textual representation and reconstructs them when working with the same ROPOT repeatedly.
For convenience, we created a Python script for inserting the editor into existing question sets. The script can also be used to remove the previous editor from question set files.
The editor has been in active use in ROPOT applications of the course IB005 since March 2021. Deployment of the editor was success- ful since no significant problems associated with the editor occurred during this time, and any minor errors were resolved quickly. We also collected feedback from students based on which we implemented changes and improvements.
In the future, the editor could be enhanced by adding functionality that could further elevate the user experience. For example, the abil- ity to undo and redo changes, allow selection of multiple elements and their manipulation at the same time, or support copy and paste functionality.
Bibliography
1. BUKOVENOVÁ, Michaela.Pohodlné vkladanie regulárnych jazykov do webového formulára. Brno, 2014. Available also from: https : //is.muni.cz/th/gl8on/. Bachelor’s thesis. Masaryk University, Faculty of Informatics.
2. ŠMÝKALA, Matúš.Pohodlné vkladanie regulárnych jazykov do we- bového formulára. Brno, 2015. Available also from:https://is.
muni.cz/th/uf06v/. Bachelor’s thesis. Masaryk University, Fac- ulty of Informatics.
3. POKLEMBA, Matej. Pohodlné vkládání regulárních jazyků do we- bového formuláře. Brno, 2016. Available also from:https://is.
muni.cz/th/t8wb3/. Bachelor’s thesis. Masaryk University, Fac- ulty of Informatics.
4. ČERNÁ, Ivana; KŘETÍNSKÝ, Mojmír; KUČERA, Antonín. For- mální jazyky a automaty I.Elportál. 2006. issn 1802-128X. Avail- able also from:http://is.muni.cz/elportal/?id=703389. 5. HOPCROFT, John E.; MOTWANI, Rajeev; ULLMAN, Jeffrey
D.Introduction to Automata Theory, Languages, and Computation.
2nd ed. New York: Springer, 1939. isbn 0-201-44124-1.
6. SIPSER, Michael.Introduction to the Theory of Computation. 3rd ed.
Cengage Learning, 2013. isbn 1-133-18779-X.
7. KOZEN, Dexter C.Automata and computability. New York: Springer, 1997. isbn 0-387-94907-0.
8. HTML[online]. Mozilla [visited on 2021-05-03]. Available from:
https : / / developer . mozilla . org / en - US / docs / Glossary / HTML.
9. HTML[online]. Mozilla [visited on 2021-05-19]. Available from:
https : / / developer . mozilla . org / en - US / docs / Web / API / Document_Object_Model.
10. CSS: Cascading Style Sheets [online]. Mozilla [visited on 2021- 05-07]. Available from:https://developer.mozilla.org/en- US/docs/Web/CSS.
BIBLIOGRAPHY
11. SVG: Scalable Vector Graphics[online]. Mozilla [visited on 2021- 05-04]. Available from:https://developer.mozilla.org/en- US/docs/Web/SVG.
12. D3: Data-Driven Documents[online] [visited on 2021-05-04]. Avail- able from:https://github.com/d3/d3/wiki.
13. D3 selections[online] [visited on 2021-05-08]. Available from:
https://github.com/d3/d3-selection/blob/v2.0.0/README.
md#selection.
14. jQuery[online] [visited on 2021-05-10]. Available from:https:
//jquery.com/.
15. ČEBIŠ, Radim.Automatická kontrola syntaxe obsahu textové oblasti ve webovém formuláři. Brno, 2008. Available also from: https : //is.muni.cz/th/vcdg7/. Bachelor’s thesis. Masaryk University, Faculty of Informatics.
16. SLOUPOVÁ, Kateřina.Reimplementace a konsolidace systémů pod- porujících výuku formálních jazyků. Brno, 2020. Available also from:
https : / / is . muni . cz / th / bwci5/. Master’s thesis. Masaryk University, Faculty of Informatics.
42
