• Unit 9: Regular Expressions and Finite-State Automata

    Computer language compilers frequently use regular languages (which feature regular expressions) to match patterns within text or perform lexical analysis. This unit will introduce formal languages and state automata to prove the correctness or falsity of a language. We will see that some languages might not be valid for a state automaton, but that we can also define and create state automata for languages defined using regular expressions.

    The definition of regular expressions is recursive. This definition and that of regular sets and regular expressions requires careful contemplation on your part.

    The topic of formal languages and the related topic of finite state automata are not directly addressed in our two references. Our study of discrete structures has given us the background to develop these topics in instruction paragraphs.

    We begin with notation, terminology, and definitions and expressions for formal languages. Then we introduce finite automata and their relationship with regular expressions, and use them to solve problems.

    Completing this unit should take you approximately 5 hours.