• Review

  

  

Regular Expression (RE)

type of language description

• DFA, NFA: “blueprint” for constructing a machine, recognizing a regular language (machile-like descriptions)
• RE: “user-friendly” way of discribing a regular language (algebraic descriptions) 즉 DFA와 동일한 regular language 를 표현하지만 방식이 조금 다르다.

components of RE

• Strings from alphabet SIGMA
• Parentheses (괄호)
• Operators
  • +: Union
  • ㆍ: concatenation
  • *: star-closure

Example of RE

Inductive Definition of RE

for given $\Sigma$

1. $\phi$, $\epsilon$, a $\in \Sigma$ : Primitive Regular Expressions
2. for RE r1 and r2, r1+r2, r1 $\cdot$ r2, r1*, (r1) are RE
3. A string is RE ↔ derived from primitive regular expressions+finite applications of rules above

Language of RE