TAILIEUCHUNG - Lecture Formal methods in software engineering: Theory of automata
This chapter presents the following content: Defining languages by another new method, regular expressions, language-defining symbols, plus sign, formal definition of regular expressions, product set, languages associated with regular expressions, how hard it is to understand a regular expression,. | Theory of Automata Qasiar Javaid Assistant Professor Lecture # 06 Defining Languages by Another New Method Regular Expressions Defining Languages by Another New Method Formal Definition of Regular Expressions Languages Associated with Regular Expressions Finite Languages Are Regular How Hard It Is to Understand a Regular Expression Introducing EVEN-EVEN Language-Defining Symbols We now introduce the use of the Kleene star, applied not to a set, but directly to the letter x and written as a superscript: x*. This simple expression indicates some sequence of x’s (may be none at all): x* = λ or x or x2 or x3 = xn for some n = 0, 1, 2, 3, Letter x is intentionally written in boldface type to distinguish it from an alphabet character. We can think of the star as an unknown power. That is, x* stands for a string of x’s, but we do not specify how many, and it may be the null string . The notation x* can be used to define languages by writing, say L4 = language (x*) Since x* is any string of x’s, L4 is then the language of all possible strings of x’s of any length (including λ). We should not confuse x* (which is a language-defining symbol) with L4 (which is the name we have given to a certain language). Given the alphabet = {a, b}, suppose we wish to define the language L that contains all words of the form one a followed by some number of b’s (maybe no b’s at all); that is L = {a, ab, abb, abbb, abbbb, } Using the language-defining symbol, we may write L = language (ab*) This equation obviously means that L is the language in which the words are the concatenation of an initial a with some or no b’s. From now on, for convenience, we will simply say some b’s to mean some or no b’s. When we want to mean some positive number of b’s, we will explicitly say so. We can apply the Kleene star to the whole string ab if we want: (ab)* = or ab or abab or ababab Observe that (ab)* ≠ a*b* because the language defined by the expression on the left contains .
đang nạp các trang xem trước
