---
title: "Learning Regular Languages via Alternating Automata"
authors:
  - "Dana Angluin"
  - "Sarah Eisenstat"
  - "Dana Fisman"
doi: ""
url: "https://ijcai.org/proceedings/2015/466"
pdf: "https://ijcai.org/proceedings/2015/0466.pdf"
venue: "Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence"
year: 2015
pages: "3308-3313"
track: "Special Track on Machine Learning"
keywords:
---

# Learning Regular Languages via Alternating Automata

Dana Angluin, Sarah Eisenstat, Dana Fisman

*Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence*, pages 3308-3313.

## Abstract

Nearly all algorithms for learning an unknown regular language, in particular the popular L* algorithm, yield deterministic finite automata. It was recently shown that the ideas of L* can be extended to yield non-deterministic automata, and that the respective learning algorithm, NL*, outperforms L* on randomly generated regular expressions. We conjectured that this is due to the existential nature of regular expressions, and NL* might not outperform L* on languages with a universal nature. In this paper we introduce UL* — a learning algorithm for universal automata (the dual of non-deterministic automata); and AL* — a learning algorithm for alternating automata (which generalize both universal and non-deterministic automata). Our empirical results illustrate the advantages and trade-offs among L*, NL*, UL* and AL*.