CS 4110 Exam 1 Weber State

1-12 Module 1

Suppose a closure is performed on a language L (in other words, the Kleene star L*). What is true of Λ in L*?

L* may have Λ

L* may have one or more Λ

L* always has Λ

L* never has Λ

L* always has Λ

Suppose an alphabet contains no words, and the language contains only the null string. What is true about the closure (i.e. the syntax using the Kleene star) of that language?

It is the empty set ∅ and infinite

It is the empty set ∅ and finite

It is the null string Λ and infinite

It is the null string Λ and finite

It is the null string Λ and finite

Suppose a language L = {a b c}. How many words of length 3 does L* have?
8

2

4

3

8
I think this question is bugged dawg. It a maka no sense. It should be 27 because 3 ^ 3 = 27

I think it’s supposed to ask how many 2 letter words. IE 2 ^ 3 = 8.

What is a recursive definition, as described in Chapter 3?

A function that calls itself.

A logical implication of the form "p implies q".

A rule 1 which explicitly uses rule 2. And a rule 2 which explicitly uses rule 1.

A base or basic starting point. Then a way to construct and place more words in the set from words already in the set. Finally stating no other elements are in the set.

A base or basic starting point. Then a way to construct and place more words in the set from words already in the set. Finally stating no other elements are in the set.

Which of the following operations are allowed in regular languages as defined in chapter 4?

Concatenation, closure (*), positive closure (+), or (|), and parenthesis grouping

Concatenation, closure(*), positive closure (+), or (+), ranges ([a..z]), zero or one (?), and parenthesis grouping

Concatenation, closure(*), and (&&), or (||), and parenthesis grouping

Concatenation, closure (*), or (+), and parentheses grouping

Concatenation, closure (*), or (+), and parentheses grouping.

Technically you can use C^+ (i.e., positive closure), but the book says it’s redundant because you can say the same with just the normal closure.

What is a good description for the following regular expression:

(a + b)*a(a + b)*b(a + b)* +

(a + b)*b(a + b)*a(a + b)*

This is not a valid regular expression

All words containing a's and b's of any number

All words containing at least one a and one b

All words containing two a's and two b's

All words containing at least one a and one b

What regular expression has an odd number of a's?

a(a+b)*a

b*ab*(aa)*b*

(a + b)*a(a+b)*a(a+b)*a(a+b)*

(ab+ba)*

b*ab*(aa)*b*

Which of the following symbols refers to an alphabet?

∅ (phi)

Σ (sigma)

Α (alpha)

Λ (lambda)

Σ (sigma)

What is a positive closure of a language, signified with the + superscript?

All permutations of words but Λ is included

Word permutations must occur only in lexicographical order

All permutations of words but Λ isn't included

Word permutations are limited to not allowing repeats

All permutations of words but Λ isn't included

For what reason does the textbook describe why recursive definitions are employed for languages?

To find the most efficient algorithm to accomplish a task

Languages are best thought as functions, and functions inherently allow recursion

To see that certain tasks are possible for a computer to do even if we do not know the best algorithms by which to do them

Because no other approach works for defining languages as they all have fundamental shortcomings

To see that certain tasks are possible for a computer to do even if we do not know the best algorithms by which to do them

What is true regarding regular languages and regular expressions?

All regular expressions haveregular languages associated with them

For all regular expressions, no regular language can be associated with them

Some, but not all, regular expressions can have regular languages associated with them

Regular expressions cannot be thought of in terms of regular languages, as they are two entirely different concepts

All regular expressions have regular languages associated with themf

What regular expression has an even number of a's and b's

(aa+bb)*

(a+b)*(a+b)*

(aa+ab+ba+bb)*

(ab)(a+b)*(ab)

(aa+bb)*