Architettura Software

Exercises on Automata and Formal Languages – Solutions and Explanations

Solved exercises on non-deterministic finite automata (NDFA): step-by-step construction with detailed explanations.

Course description

Practical Exercises on Non-Deterministic Finite State Automata

Theoretical computer science intimidates many, but with the right guidance it becomes a fascinating logical puzzle. This series of solved exercises guides you step by step through the construction of non-deterministic finite state automata (NDFA) starting from the formal definition of the language — exactly as required in university courses.

What's in This Course

  • 15 progressive exercises on NDFA, solved with detailed explanations
  • Automaton construction from formal language definitions: L=(a+b)*b(a+b), L=(ab)*+(ba)* and others
  • Handling linear chains, loops, non-accepting states and sequences to avoid
  • Exercises on languages with cardinality constraints (even number of b's, odd number of a's)
  • Explanation of the reasoning, not just the result

Why These Exercises Work

This is not a theoretical course: I start from the formal language, draw the automaton, and explain every transition. If you have an exam in Theoretical Computer Science or Formal Languages, this series gives you exactly the hands-on practice that textbooks lack.

Who This Course Is For

University students in computer science or software engineering who need to consolidate automata theory through practical exercises.

Lessons list

Let's build a Nondeterministic Finite State Automaton (NFSA) step by step from the language L=(a+b)*b(a+b): a simple linear chain to start reasoning about transitions in nondeterministic automata.

Guarda lezione

Let's solve an NFSA exercise for the language L=(ab)*+(ba)*: a simplified double state chain with two alternative branches, showing how to correctly model both paths in the automaton.

Guarda lezione

Let's build the automaton for L=(aa)*+(bb)*: a double state chain that introduces the distinction between the two alphabet symbols and shows how to handle parallel branches in the automaton.

Guarda lezione

Let's solve the exercise for L=(ab)*+(aab)*: a more articulated double state chain where the two branches have sequences of different lengths, walking through the reasoning behind each transition.

Guarda lezione

Let's build the automaton for L=(abc)*: a state chain with a loop that shows how to handle repeated three-symbol sequences in a nondeterministic finite state automaton.

Guarda lezione

Let's tackle a language that forbids three consecutive c symbols: we'll see together how to build an NFSA capable of recognizing valid strings and rejecting those that violate the constraint.

Guarda lezione

Let's build the automaton for a language with a non-accepting terminal state: strings must end with 'bc' and must not contain 'ccc' — I'll explain how each constraint maps to transitions and states.

Guarda lezione

Let's solve an NFSA exercise with cardinality constraints: an even number of b's and an odd number of a's. I'll walk through building the automaton step by step, reasoning through every possible combination.

Guarda lezione
Giovanni Pace

Giovanni Pace

Ingegnere Informatico · Pratola Peligna

  • 107 Courses
About the teacher

Sono un ingegnere informatico con oltre 15 anni di esperienza nel settore ICT. Mi occupo di sviluppo software, cybersecurity, data science e intelligenza artificiale, con particolare attenzione all’innovazione e all’automazione dei processi aziendali. Da anni svolgo anche attività di docenza e formazione, creando percorsi pratici e coinvolgenti su programmazione, DevOps, AI e sicurezza informatica.

This course includes

  • Lessons 8
  • Duration 0h 54m
  • Difficulty intermedio
  • Language it
  • Certificate No

Recently viewed