Dr. Justin James to present this week’s Undergraduate Math Seminar
Wednesday, Feb. 15 | 4-4:50 p.m. | Bridges 268
Featuring Justin James | Formal Languages, Finite State Automata, and Regular Expressions
What is needed in order to form a language? In their most basic form, languages require an alphabet (a set of letters) and a collection of finite strings of letters called words. In order to recognize a language, one must be able to distinguish strings of letters that form words from those that do not form words. Although this sounds straightforward at first glance, one should note that if we allow words of arbitrary (finite) length, there are infinitely many potential words to consider. In this talk, we will discuss both the collection of languages recognized using simple computational machines called Finite State Automata and the collection of languages defined inductively using regular operations. Perhaps surprisingly, these end up being the same collection of languages. We will then discuss a few properties of these languages and establish the fact that not every language has this form.