What is a Regular Expression?

It is a way of denoting/describing languages. EX: $(0{\cup}1)0^*$ is an example of a regular expression. Says that the language starts with a 0 or a 1 followed by any number of 0s.

Rules for regular expression:

  1. Empty set ${\empty}$ is a regular expression and denotes language ${\empty}$.
  2. Empty string ${\lambda}$ is a regular expression denoting set {${\lambda}$}.
  3. Each alphabet a is a regular expression and denotes the set {${a}$}.
  4. If r and s are regular expressions, then r + s denotes the set ${r \cup s}$.
  5. if r and s are regular expressions, then rs denotes concatenation r with s.
  6. r* is a regular expression denoted by set ${r^0 \cup r^1 \cup r^2 \cup … r^n}$

Look at given examples in notebook.

What is a Non-regular Language?

List of Non-regular Languages:

  1. $L_1 =$ {$a^nb^n | n>=0$}
  2. $L_2 =$ {$a^nb^{(n+2)} | n >= 0$}
  3. $L_3 =$ {$b^na^{(n+4)} | n > 0$}
  4. $L_4 =$ {$ww^r | w \in (a+b)^*$}

What is Pumping Lemma for Regular Languages?

It is used to prove nonregularity of regular languages. The pumping lemma will state that all regular languages will have this property–if we can show that a language does not have this property, then it is guaranteed to not be regular. Let L be an infinite regular language. Then there exists some positive integer m (construct of pumping lemma) such that for any $w{\in}L$ with ${|w| >= m}$ can be decomposed into 3 parts:

THIS IS AN IMPORTANT THING TO KNOW!!!

Definition of Pumping Lemma:

If A is a regular language, then there is a number p (the pumping length) where, if s is any string in A of length at least p, then s may be divided into three pieces, s = xyz where it satisfies the three conditions:

  1. for each i >= 0, ${xy^iz \in A}$
  2. $|y| > 0$
  3. $|xy| <= p$
  • Examples in notes–read it!

Context-Free Grammar (CFG)

A context free grammar (CFG) ($G = (V, T, P, S)$) is a 4-tuple where:

  1. V = finite set of variables
  2. T = finite set of terminals
  3. P = finite set of production
  4. $S{\in}V$ is the start symbol

Conversions:

  • Capital letters A, B, C, D, S, etc. are used for variables.
  • Lowercase letters a, b, c, 1, 2, 3, … are used for terminals
  • X, Y, Z, may be used either for terminal or for variables