Regular Language

A formal language that can be expressed through regular expressions (regex) in their strict sense.

6 flashcards · Mathematics · by lakesare

1. Name 2 ways to define a regular language L.

   A formal language is called a regular language: if there exists some finite-state machine that accepts this language L(A). if it can be described by a regular expression. That is, if all strings in L(A) set lead an A into an accepting state.

2. How are regular expressions that can be used to define regular language different from usual, e.g. Ruby's, regexes?

   Many regular expressions engines provided by modern programming languages are augmented with features that allow recognition of languages that cannot be expressed by a classic regular expression.

3. Define a regular expression (3 bases, 3 recursions).

   Base: ∅ (empty set), ε (0-length string), each individual symbol in ∑ are regular expressions over ∑. Recursion: (r s) - concatenation of r and s (r∗) - concatenation of r with itself 0 or more times (r | s) - either r or s. Nothing is a regular expression except for objects above.

4. The formal definition of regular expressions is purposely parsimonious and avoids defining the redundant quantifiers. Express a? and a+ through formal quantifiers.

   a? = (a|ε) a+ = aa*

5. A number of shorthand commands for regexes exists in computer languages. What do these stand for: [A − C] [0-9] r{m, n} .

   [A − C] - (A | B | C) [0 − 9] - (0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9) r{m, n} - concatenation of r m to n times . - any letter of the alphabet ∑

6. Regexes: start of the string VS negation?

   Start of the string: let str1 = "Mary had a little lamb"; alert( /^Mary/.test(str1) ); // true Negation: /[^abc]/ That will match any character except for a b or c. When used inside [ and ] the ^ (caret) is the not operator.