An introduction to graphs, formal languages and automata

Undergraduate course, IUT Orsay, 2019

An introduction to graph theory concluding with an introduction to automata and formal languages.

Graph Theory

  • Generality: oriented and un-oriented graphs, valued graphs, sub-graphs, degree, chain, path, connexity, strong connexity
  • Graph traversal: Depth-first search, Breadth-first search
  • Shortest path: Dijkstra algorithm
  • Maximal flow problem: Flow, Cut, Maximum flow, Minimal cut, Ford-Fulkerson algorithm

Formal Languages

  • Alphabet and words
  • Regular language, regular expressions

Automata

  • Synchronus and Asynchronus automata
  • Determinist automata
  • Automata and regular languages
  • Unambiguous finite automata