![]() ![]() "d(ca)*b" generates strings db, dcab, dcacab, dcacacab, and so on. ![]() Similar to standard Algebra, parentheses can be used to group sub-expressions.įor example, "dca*b" generates strings dcb, dcab, dcaab, and so on, whereas The order of precedence for Regular Expression operators is: Kleene Star, concatenation, and then union. if a and b are both REs, then so are the strings built up using the following rules:Ī. If the string a is in the input alphabet, then it is a RE. The rules for forming a Regular Expression (RE) are as follows:ġ. For example, the regular expression corresponding to the first FSA given above is xx*yy*. The FSA above will accept strings composed of one or more x’s followed by one or more y’s (e.g., xy, xxy, xxxyy, xyyy, xxyyyy).Ī Regular Expression (RE) is an algebraic representation of an FSA. In State C, seeing any additional letter y will keep the machine in state C. State C is a final state so if the string being parsed is completed and the FSA is in State C, the input string is said to be accepted by the FSA. Once in state B, there are two transition rules: seeing the letter y will cause the FSA to make C the active state, and seeing an x will keep B as the active state. The only way to go from state A to B is by seeing the letter x. ![]() The initial state is A the final state is C. In the above FSA, there are three states: A, B, and C. Here is a drawing of an FSA that is used to parse strings consisting of x's and y's: ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |