Page 1 1 Regular Expressions Page 2 1 Regular Expressions 2 Regular Expressions vs. Finite Automata n Offers a declarative way to express the pattern of any string we want to accept n E.g., 01*+ 10* n Automata => more machine-like < input: string , output: [accept/reject] > n Regular expressions => more program syntax-like n Unix environments heavily use regular expressions n E.g., bash shell, grep, vi & other editors, sed n Perl scripting – good for string processing n Lexical analyzers such as Lex or Flex Page 3 1 Regular Expressions 2 Regular Expressions vs. Finite Automata n Offers a declarative way to express the pattern of any string we want to accept n E.g., 01*+ 10* n Automata => more machine-like < input: string , output: [accept/reject] > n Regular expressions => more program syntax-like n Unix environments heavily use regular expressions n E.g., bash shell, grep, vi & other editors, sed n Perl scripting – good for string processing n Lexical analyzers such as Lex or Flex 3 Regular Expressions Regular expressions Finite Automata (DFA, NFA, e-NFA) Regular Languages = Automata/machines Syntactical expressions Formal language classes Page 4 1 Regular Expressions 2 Regular Expressions vs. Finite Automata n Offers a declarative way to express the pattern of any string we want to accept n E.g., 01*+ 10* n Automata => more machine-like < input: string , output: [accept/reject] > n Regular expressions => more program syntax-like n Unix environments heavily use regular expressions n E.g., bash shell, grep, vi & other editors, sed n Perl scripting – good for string processing n Lexical analyzers such as Lex or Flex 3 Regular Expressions Regular expressions Finite Automata (DFA, NFA, e-NFA) Regular Languages = Automata/machines Syntactical expressions Formal language classes 4 Language Operators n Union of two languages: n L U M = all strings that are either in L or M n Note: A union of two languages produces a third language n Concatenation of two languages: n L . M = all strings that are of the form xy s.t., x Î L and y Î M n The dot operator is usually omitted n i.e., LM is same as L.M Page 5 1 Regular Expressions 2 Regular Expressions vs. Finite Automata n Offers a declarative way to express the pattern of any string we want to accept n E.g., 01*+ 10* n Automata => more machine-like < input: string , output: [accept/reject] > n Regular expressions => more program syntax-like n Unix environments heavily use regular expressions n E.g., bash shell, grep, vi & other editors, sed n Perl scripting – good for string processing n Lexical analyzers such as Lex or Flex 3 Regular Expressions Regular expressions Finite Automata (DFA, NFA, e-NFA) Regular Languages = Automata/machines Syntactical expressions Formal language classes 4 Language Operators n Union of two languages: n L U M = all strings that are either in L or M n Note: A union of two languages produces a third language n Concatenation of two languages: n L . M = all strings that are of the form xy s.t., x Î L and y Î M n The dot operator is usually omitted n i.e., LM is same as L.M 5 Kleene Closure (the * operator) n Kleene Closure of a given language L: n L 0 = {e} n L 1 = {w | for some w Î L} n L 2 = { w 1 w 2 | w 1 Î L, w 2 Î L (duplicates allowed)} n L i = { w 1 w 2 …w i | all w’s chosen are Î L (duplicates allowed)} n (Note: the choice of each w i is independent) n L* = U i=0 L i (arbitrary number of concatenations) Example: n Let L = { 1, 00} n L 0 = {e} n L 1 = {1,00} n L 2 = {11,100,001,0000} n L 3 = {111,1100,1001,10000,000000,00001,00100,0011} n L* = L 0 U L 1 U L 2 U … “i” here refers to how many strings to concatenate from the parent language L to produce strings in the language L iRead More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!

18 videos|43 docs|39 tests