Which of the languages below is the described by the regular expression

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Multiple choice questions

No explanation is needed for any of the questions in this section. Please select the correct answer(s) only.

1. Let Σ =   a, b    be an alphabet and n N. What is the number of possible strings of length 2n over Σ? Choose the correct answer. (8 pt)

(a) 2n!

(b) n2n

(c) 2nn

(d) 22n

2. Which of the languages below is the described by the regular expression (0 + 1)∗1(0 + 1)∗1(1 + 0)∗? Choose the correct answer. (8 pt)

(a) The set of all strings containing the substring 11.

(b) The set of all strings containing at most two 1’s.

(c) The set of all strings containing at least two 1’s.

(d) The set of all strings that begin and end with either 0 or 1.

 

 

3. At least one of the following statements are correct. Choose the correct statement(s). (8 pt)

(a) For every language L ⊆ Σ∗, ((∅ ∪ ∅) • L∗ = {ε}).

(b) For every language L ⊆ Σ∗, (∅ • L∗ = {ε}).

(c) For every language L ⊆ Σ∗, (∅ ∪ L+ = L∗)

(d) For every language L ⊆ Σ∗, (({ε} ∩ ∅) • L∗ = {ε}).

(e) For every language L ⊆ Σ∗, ({ε} ∪ L+ = L∗)

 4. Which of the grammmars below generates the language accepted by the following NFA? Choose the correct answer. (8 pt)

(a) S → aSb | bSa | SS | ε

(b) S → aS | bS | a | b

(c) S → aS | bS | ε

(d) S → aS | Sb | S | ε

5. Let L =   apbqar   q = p +r  .  Which of the grammmars below generates L?  Choose the correct answer.

S → BA

A → 0A1 | ε B → 1B0 | ε

S → AB

A → 0A1 | ε B → 1B0 | ε

S → ASBS

A → 01A | ε B → B10 | ε

S → ABC

A → 0A1 | ε B → 1B0 | ε C → a

 Regular questions

When answering questions in this section, you need to follow the given format. Fill in the empty sections that I provide below each question without skipping any of them.

6. The following languages are not regular.  Complete the missing parts of their proofs of nonregularity.

(15 pt)

(a) L = {aibj  | i = 2j}.

i. Let n > 0.

ii. Let z =?. Note that z ∈ L and |z| ≥ n.

iii. Consider z = uvw such that |uv| ≤ n and |v| ≥ 1.

iv. ?

 

 

 

 

 

v. L is not regular.

(b) L = {w ∈ {a, b, c}∗  | w  is a palindrome (i.e.  w = wR)}.

i. Let n > 0.

ii. Let z =?. Note that z ∈ L and |z| ≥ n

iii. Consider z = uvw such that |uv| ≤ n and |v| ≥ 1.

iv. ?

v. L is not regular. 

7. In this question, you will remove ε-productions from the following production grammar. (15 pt)

S → aSb | bSa | SS | ε

(Note: V = {S} and Σ = {a, b})

• Nullable symbols?

• Eliminate nullable symbols?

8. In this question, you will design a CFG for the language L = {anbm | m ≥ n, m − n is even}. (15 pt)

• Give the recursive definition?

– Basis: ?

– Recursive step: ?

• List the rules of the CFG: ?

 9. Convert each of the following regular expressions to equivalent NFAs. (15 pt)

(a) (bab + aabaa)∗. Construct the NFA according to following steps. Do not skip any step.

• NFA for a:

• NFA for b:

• NFA for bab:

• NFA for aabaa:

• NFA for (bab + aabaa):

• NFA for (bab + aabaa)∗:

(b) (ba)∗ • (aab)∗. Construct the NFA according to following steps. Do not skip any step.

• NFA for a:

• NFA for b:

• NFA for ba:

• NFA for (ba)∗:

• NFA for aab:

• NFA for (aab)∗:

• NFA for (ba)∗ • (aab)∗:

 

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of