Regular expressions

Question 1

what is a regular expression and give an example

Answer 1

An expression describing a language generated using regular operations (union,
concatenation and star)

For example : (0 ∪ 1)◦0∗

Question 2

What are the different ways to specify languages

Answer 2

i) If the language is finite you can just list its strings eg L = {a, aa, aba, aca}
ii) Descriptive eg L = {x | x ends with 0 or 1}
iii) Using regular expressions L= {aa, ab}* ∪ {b}

Question 3

Describe the equivalence of regular expressions and automata

Answer 3

RE and FA are equivalent in their descriptive power.
A regular expression can be converted into an FA that recognizes the language it describes and vice versa

Question 4

Define a regular language

Answer 4

One that is accepted by some FA or described by some RE

Question 5

Give the different applications of regular expressions

Answer 5

Regular expressions have an important role in computer science applications.
– Specify piece of programming language, e.g. real number. This allows automated production
of tokenizer for identifying the pieces.
– Complex search and replace - awk and grep (on LINUX /UNIX systems)

Question 6

Converting a regular expression to an NFA using Thompson’s Algorithm

Answer 6

https://www.youtube.com/watch?v=pUYQejZvYPE

Question 7

Describe the The Pumping Lemma theorem

Answer 7

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

for each i ≥ 0, xyiz ∈ A.
|y| > 0, and
|xy| ≤ p.