Mathematics Undergraduate Seminar Series presents “Formal Languages, Finite State Automata, Regular Expressions, and Computational Problems in Mathematics (Part I)” today
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.
Mathematics Undergraduate Seminar Series presents: “Formal Languages, Finite State Automata, Regular Expressions, and Computational Problems in Mathematics (Part I)”
Wednesday, Feb. 11 | 3-3:50 p.m. | Bridges 268
By Justin James, MSUM