Mathematics Undergraduate Seminar Series presents “Formal Languages, Finite State Automata, Regular Expressions, and Computational Problems in Mathematics (Part II)” today
In part I of this series, we introduced formal language theory, focusing on languages that are recognized by simple computational machines called Finite State Automata. In part II, we turn our attention to how Finite State Automata (FSA) can be used to solve computational problems in groups. In particular, we discuss how to decide both the word problem and the generalized word problem in the free group on two letters. The solution to the word problem involves building a large enough portion of the Cayley Graph of the free group and thinking of it as a FSA . The solution to the generalized word problem involves building a FSA by “folding” the loop automaton for the generating words. No previous knowledge of Finite State Automata or Group Theory will be necessary to follow our discussion.
Mathematics Undergraduate Seminar Series presents: “Formal Languages, Finite State Automata, Regular Expressions, and Computational Problems in Mathematics (Part II)”
Wednesday, Feb. 18 | 3-3:50 p.m. | Bridges 268
By Justin James, MSUM