In our former series of articles, we looked at the basics of lexical analysis. In this article, we will start the series concerning syntax analysis. In the first article concerning lexical analysis, we said that we can identify tokens/patterns with the help of regular expressions and pattern rules. There is, though, a limit to lexical analysis — while we can look at the individual tokens, but it cannot check the syntax of a given sentence. Therefore, we need syntax analysis. We will start by giving both an informal and formal definition of context-free grammar.

Defining Context-Free Grammar

Imagine that you…


In the former articles, we have been introduced to both Regular Expressions and Finite Automata’s. We have also seen how we can convert an NFA to its DFA equivalent. In this article, we will combine the knowledge we have obtained from all the former articles, and we will try to represent Regular Expressions as a DFA. We will start by showing how some very simple Regular Expressions can be shown as an NFA. Then we can use these examples as building blocks as we move on to more advanced examples. …


In the former two articles, we have been introduced to both Regular Expressions and Finite Automata’s. In this article, we will try to understand how we can convert an NFA to a DFA. This will be used in the next article, where will see how we can express Regular Expressions through a DFA — but we will need to know how to convert from an NFA to a DFA. So, let us start.

The Idea Behind

It is possible to say that every DFA is an NFA, but not every NFA is a DFA. However, every NFA has a DFA equivalent. That means…


In the former article, we talked about one of the complete basic concepts in Lexical Analysis: Regular Expressions. In this article, we will expand our knowledge of Lexical Analysis and talk about Finite Automata — both Non-Deterministic (NFA) and Deterministic (DFA). We need to understand these concepts and in the next article, we will explore how we can convert an NFA to a DFA.

The Concept of Finite Automata

Let us first understand the concept of a Finite Automata itself before we continue. A Finite Automata is basically an abstract machine — it is the simplest machine to recognize patterns…


In this article, we will talk about one of the most basic subjects in Lexical Analysis: Regular Expressions, which are also called Regex. This will create the foundation for the coming articles, where we will explore what Non-Deterministic and Deterministic Finite Automata’s are — and how they can be used to represent Regular Expression. But first — we will need to define what is meant by Regex.

Regular Expressions

The question is — what is a regular expression and what is it used for? Regular Expressions, also called Regex, are extremely effective in extracting information from a text. In other words, Regular…


In former articles, we looked at various kinds of graphs and algorithms defined upon them. We defined the two algorithms: Prim’s and Kruskal’s algorithm. They are both used for the same purpose — finding the minimum spanning tree of a weighted graph but offer two different methods. In this article, we will look at Dijkstra’s Algorithm. It is used to find all the shortest paths from the chosen root to all vertices in the given graph. We will see how the algorithm works in this article and compare it to the two former methods. …


In a former article, we looked at various kinds of graphs. We defined various forms of graphs, including weighted graphs and minimum spanning trees. These two kinds of graphs will be relevant in this article, where we will introduce two algorithms: Prim’s and Kruskal’s Algorithm. They are both used for the same purpose — finding the minimum spanning tree of a weighted graph but offer two different methods. These two methods will be presented in this article, and we will try to understand what situations call for which algorithm. …


In the former article, we saw some of the basic concepts in graph theory. These concepts will come in handy in this, and following, articles, where we will see some more advanced algorithms which can be defined on graphs. In this article, we will look at two of the most basic graph-algorithms: breadth-first search and depth-first search.

Levels in Graphs and Trees

Before we start talking about Breadth and Depth First search, we will first need to understand another basic concept in graph theory. We need to understand the concepts of dividing trees and graphs into levels. It is a…


In this article, we will get a quick introduction to the basics of graph theory. We will talk about graphs in general — and the two classes they can fall into directed or undirected graphs. Afterward, we will also tackle another form of graphs — trees and so-called minimum spanning trees. This will all serve as the theoretical foundations for this series of articles where we will try to understand various algorithms which function upon graphs — for example, Depth and Breadth-First Search.

Graphs and Their Representation

Firstly, we need to understand what a graph is — and how we…


In the former articles, we considered the sub-category, combinations, in the theory of counting. We saw multiple theorems and how they could be applied to real-world problems. In this article, we will tackle the subject of combinations. Combinations are much like permutations, with one key difference — in permutations the order of the items matters, while it does not in combinations. Therefore, we will only need to consider the two following theorems.

Combinations — without repetitions

Imagine that we have a set, S, which contains n elements. We want to find the total number of possible combinations when we consider…

Naja Møgeltoft

Data science and Machine Learning student at Copenhagen University.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store