Language & Regular Expressions

Question 1

Alphabet

Answer 1

A finite set of fundamental units, Σ

Question 2

Language

Answer 2

A set of strings of symbols from the alphabet, plus rules specific to the language

Question 3

Words

Answer 3

Finite strings that are permissible in the language generated from the alphabet and the rules of the language

Question 4

empty, null string symbol

Answer 4

lowercase epsilon ε or uppercase lambda Λ

Question 5

Concatenation

Answer 5

Joining character strings end-to-end

Question 6

Palindromes

Answer 6

A word, phrase, number or sequence of words that reads the same backwards as forwards

Question 7

Closure Kleene Star

Answer 7

A programming resource that offers outcomes related to the concatenation

Question 8

Regular expressions

Answer 8

A sequence of characters that define a search pattern

Question 9

Rule 1 of defining regular expressions

Answer 9

If x ∈ Σ then x is a regular expression

Question 10

Rule 2 of defining regular expressions

Answer 10

If r1 and r2 are regular expressions then so are (r1), r1r2, r1|r2, r1*

Question 11

Rule 3 of defining regular expressions

Answer 11

Nothing else is a regular expression

Question 12

When can only 2 regular expressions be equivalent?

Answer 12

If and only if they describe the same language

Question 13

Rule 1 for language to be associated with a regex

Answer 13

If r is a regex, then language(r) = {r}

Question 14

Rule 2 for language to be associated with a regex

Answer 14

If L1 = language(r1) and L2 = language(r2), the (r1r2) = L1L2, (r1|r2) = L1|L2, (r1) = L1