Chapter 2 - Formal Languages

Question 1

What does epsilon signify in LAC?

Answer 1

Epsilon = the empty word i.e. a sequence of length 0

Question 2

What does sigma mean in LAC?

Answer 2

Sigma = a finite set of symbols

Question 3

What does sigma star represent in LAC?

Answer 3

Sigma star = set of words over sigma, including the empty word

Question 4

For any nonempty alphabet (sigma), what is the length of sigma star?

Answer 4

Sigma star is an infinite set

Question 5

What is a language in LAC?

Answer 5

A condition which words must satisfy to be included within the language stated, such as the set of words that contain the same number of 0s and 1s is a language over (sigma = {0,1})

Question 6

What is the difference between epsilon, theta and {epsilon}?

Answer 6

Epsilon denotes the empty word
Theta denotes the empty set i.e. a set with no elements
{epsilon} is a set with exactly one element - the empty word