Module 1: Regular Expressions

Question 1

What does a lexer do in programming languages?

Answer 1

The lexer is used to check the syntax of the code in a particular programming language.

It separates the nouns and verbs in a programming language.

Question 2

What is the input into a lexer?

Answer 2

Inputs that go into a lexer are a series of bytes. (Just the program as bytes)

Question 3

What are tokens in a programming language and what are they made of?

Answer 3

Tokens are meaningful words in a programming language. Tokens are made up of a series of strings.

Question 4

What does a compiler writers do?

Answer 4

The compiler writers can understand and enforce the syntax

Question 5

What is the output of a lexer?

Answer 5

It is a series of strings that make up tokens.

Question 6

What is a string and how do we define a string over an alphabet ∑ (sigma)?

Answer 6

A string is alphabet symbols together.

A string over an alphabet ∑ (sigma) is a finite sequence of symbols from ∑ (sigma)

Question 7

How is an ɛ (empty string) defined?

Answer 7

It is a string that is an ɛ empty sequence of symbols.

Question 8

What happens if you concat a string with an ɛ empty string?

i.e. ɛs = s ɛ

Answer 8

When you concat a string with an ɛ you will get the string back. This does not matter the order of the operation at this point, the empty string can come first or last in the arithmetic operation.

ɛs = s ɛ = s

Question 9

What does ∑* stand for?

Answer 9

The star operator contains all of the possible possibilities of combinations given a set.

So ∑* contains all of the strings that can be created by combining the alphabet symbols into a string.

Question 10

Is language L a subset of ∑*?

Answer 10

Yes, language L is a subset of ∑*

Question 11

Which of the following are infinite?

a. ∑
b. ∑*
c. L

Answer 11

b. ∑* is infinite

c. L can be both finite and infinite

Question 12

Why do we need regular expressions?

Answer 12

We need regular expressions because tokens are typically specified using regular expressions.

Question 13

Which of the following apply to regular expressions?

a. Compact
b. Expressive
c. Declarative
d. Vague
e. Precise
f. Widely used
g Hard to generate
h. Easy to generate

Answer 13

a. Compact
b. Expressive (expandable)
e. Precise (not ambiguous, will not match two specific defs)
f. Widely used
h. Easy to generate

Question 14

What does compact mean in mathematics?

Answer 14

Compact means a set with no holes in it.

Question 15

Which of the following are rules that a regular expression will follow:

a. Ø
b. ɛ
c. a, where a is not an element in the alphabet
d. a, where a is an element in the alphabet
e. R1 * R2, where R1 and R2 are regular expressions
f. R1 | R2, where R1 and R2 are regular expressions
g. R1 . R2, where R1 and R2 are regular expressions
h. (R), where R is a regular expression
i. R*, where R is a regular expression

Answer 15

a. Ø (null set)
b. ɛ
d. a, where a is an element in the alphabet
f. R1 | R2, where R1 and R2 are regular expressions
g. R1 . R2, where R1 and R2 are regular expressions
h. (R), where R is a regular expression
i. R*, where R is a regular expression

Question 16

What is the cardinality of an empty string?

a. 0
b. 1
c. -1
d. 2

Answer 16

b. 1

Question 17

Which of the following are true:

a. L(Ø) = 0
b. L(Ø) = Ø
c. L(ɛ) = { }
d. L(a) = { }
e. L(R1 | R2) = L(R1) U L(R2)
f. L(R1 . R2) = L(R1) . L(R2)

Answer 17

b. L(Ø) = Ø
c. L(ɛ) = { }
d. L(a) = { }
e. L(R1 | R2) = L(R1) U L(R2)
f. L(R1 . R2) = L(R1) . L(R2)

Question 18

What does L(a | b) equal?

a. L(a) | L(b)
b. L(a) U L(b)
c. {a} U {b}
d. {a,b}

Answer 18

b. L(a) U L(b)
c. {a} U {b}
d. {a,b}

Question 19

What does (a | b | c) equal?

a. L(a|b) U L(c)
b. L(a) | L(b) | L(c)
c. {a,b} U {c}
d. {a,b,c}

Answer 19

a. L(a|b) U L(c)
c. {a,b} U {c}
d. {a,b,c}

Question 20

What does L(a | ɛ) equal?

a. L(a)
b. L(ɛ)
c. L(a) U L(ɛ)
d. {a}
e. {a} U {ɛ}
f. {a,ɛ}

Answer 20

c. L(a) U L(ɛ)
e. {a} U {ɛ}
f. {a,ɛ}

Question 21

What does L(ɛ|ɛ) equal?

a. Null
b. {ɛ}

Answer 21

b. {ɛ}

Question 22

What does the A . B equal given:
A = {aa, b}
B = {a,b}

a. {aa,a,b}
b. {aab,b,a,b}
c. {aaa,aab,ba,bb}
d. {aaa,ba,baa,bb}

Answer 22

c. {aaa,aab,ba,bb}

Question 23

What does the A . B equal given:
A = {aa, b, ɛ}
B = {a,b}

a. {aaa,aab,ba,bb}
b. {ɛ}
c. {aaa,aab,ba,bb,a,b}
d. {aaa,ab,a,baa,bb,b}

Answer 23

c. {aaa,aab,ba,bb,a,b}

Question 24

In order of operations what comes first in the following:

L(a | b .c)

a. a | b
b. b . c

Answer 24

b. b . c

Question 25

What does L(a | b . c) evaluate to?

a. {a , bc}
b. {abc}
c. {b, ac}
d. {ab, c}

Answer 25

a. {a , bc}

L(a) U L(b . c) = {a} U {bc} = {a, bc}

Question 26

What is the Kleene Star operator?

Answer 26

The kleene star operator is the * symbol that is used to indicate an infinite set.

Question 27

What is the definition of L(R*)?

a. L^(i-1) . L(R)
b. U(subset i>=0) L^(i)(R)

Answer 27

b. U(subset i>=0) L^(i)(R)

Question 28

What does L(a | b*) equal?

a. {b,bb,bbb,bbbb,…}
b. {a,b,bb,bbb,bbbb,…}
c. {a, ɛ,b,bb,bbb,bbbb,…}

Answer 28

c. {a, ɛ,b,bb,bbb,bbbb,…}

Question 29

What does L((a | b)*) equal?

a. {ɛ}
b. {ɛ} U {a,b}
c. {a,b} U {aa,ab,ba,bb} U {aaa,aab,aba,baa,bab,bba,bbb} U …
d. {ɛ} U {a,b} U {aa,ab,ba,bb} U {aaa,aab,aba,baa,bab,bba,bbb} U …

Answer 29

d. {ɛ} U {a,b} U {aa,ab,ba,bb} U {aaa,aab,aba,baa,bab,bba,bbb} U …

The third is found by concating {a,b} . {a,b}.

The forth is found by concating {aa,ab,ba,bb} . {a,b}

Question 30

Which of the following are valid ID’s given the following:

letter = a | b | c | d | e | ... | A | B | C | D | ...
digit = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
ID = letter(letter | digit | _ )*

a. a891_jksdbed
b. 12ajkdfjb

Answer 30

a. a891_jksdbed

Question 31

How do we define a number given:
digit = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
pdigit = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

a. NUM = digit*
b. NUM = digit(digit)*
c. NUM = pdigit(digit)*
d. NUM = pdigit(digit)* | 0

Answer 31

d. NUM = pdigit(digit)* | 0

Question 32

What is the longest matching prefix rule?

a. Starting from the next input symbol, find the longest string that matches a token.
b. Starting from the first input symbol, find the longest string that matches a token.

Answer 32

a. Starting from the next input symbol, find the longest string that matches a token.

Question 33

What happens when you have a tie in the longest matching prefix rule?

Answer 33

If there is a tie between two prefix rules, then you use whichever rule was defined first in the rule list.