The + operator in regular expressions is used in some books to denote one or more applications of Kleene star.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Exercise 1: Regular Expressions........... 20 marks

Regular Expressions Syntax: The + operator in regular expressions is used in some books to denote one or more applications of Kleene star. However, in other places, such as JFLAP, + denotes the alternation operator, equivalent to  . For the purpose of this assignment, we follow JFLAP and use operator + to denote an alternation. In JFLAP, you can use λ or g to denote the empty string (see Preferences menu).

For parts (i) to (iii), please type each word on a new line. The notation wi wj denotes concatenation of words

wi and wj , and wr denotes the word obtained by reversing w.

(a) Let R1 = 1(1∗ + 2∗ )3∗ (2∗ + 3)1∗2(1 + 3)∗2∗ and R2 = 1∗3(2 + 3)∗2∗ (1 + 3)∗ (1 + 3)∗ be two regular expressions.

Whenever asked to provide words, these must be non-empty ones (and different if more than one).

1. (2 marks) [E1-Qa1.txt] Give two non-empty words w1 and w2 such that {w1, w2} ⊆ L(R1) ∩ L(R2).

2. (2 marks) [E1-Qa2.txt] Give two non-empty words w1 and w2 such that {w1, w2} ⊆ L(R1) L(R2).

• (2 marks) [E1-Qa3.txt] Give two non-empty words w1 and w2 such that {w1, w2} ⊆ L(R2) L(R1).

4. (1 mark) [E1-Qa4.txt] Give a non-empty word w ∈ L(R1) such that w wr ∈ L(R1).

5. (1 mark) [E1-Qa5.txt] Give a non-empty word w ∈ L(R1) such that w wr g L(R1).

6. (1 mark) [E1-Qa6.txt] Give a regular expression R such that L(R) = L(R1) ∪ L(R2).

• (3 marks) [E1-Qa7.txt] Give a regular expression R such that L(R) = L(R1) ∩ L(R2).

(b) Give regular expressions for the following languages.

1. (2 marks) [E1-Qb1.txt] L1 = {a3n+2bm+1 | n ≥ 1, m ≥ 0, m mod 2 = 1}.

   2. (2 marks) [E1-Qb2.txt] L2 = L1, where L is the complement of L (assume alphabet Σ = {a, b}).

• (2 marks) [E1-Qb3.txt] L = {w | w ∈{a, b}∗, |w | mod 3 = 2}, where |w | denotes the length of w.

4. (2 marks) [E1-Qb4.txt]

L = {bnw1 | n > 1, w1 ∈ (({a, c }∗ ∩ {a, b, c }∗ ) ({b}∗ ∪ {c }))} ∩ {w2c | w2 ∈ {a, b, c }∗}.

Exercise 2: Grammars............ 20 marks

• Provide regular expressions for the following

  1. (3 marks) [E2-Qa1.txt] Give a regular expression R such that L(R) = L(G1), where G1 is:

S → AcB

A → ac   |  bC   |  g

B → baB   |  caB   |  D C  → bC   |  g

D → aD | b

2. (3 marks) [E2-Qa2.txt] Give a regular expression R such that L(R) = L(G2), where G2 is:

S  → ACS   |  g

A → aA  |  bA  |  bB B → cB   |  g

C  → bcC   |  acC   |  D D → bD   |  g

• (2 marks) [E2-Qa3.txt] Give a regular expression R such that L(R) = L(G1) ∪ L(G2).

4. (2 marks) [E2-Qa4.txt] Give a regular expression R such that L(R) = L(G1) ∩ L(G2).

• Let G3 = ({S }, {a, b}, Γ, S ) be a grammar, where the set of rules Γ is defined as follows:

S  → aSbSa S  → bSbSa S  → aSbSb S  → g

1. (4 marks) [E2-Qb1.txt] Does there exist a regular expression R such that L(R) = L(G3)? If it exists, provide such R; otherwise, simply put 0.

• Let L = {c2n−1amc3b2m+1an | n, m > 0}.

  1. (3 marks) [E2-Qc1.txt] Complete the following context-free grammar G such such L(G ) = L.

S → ccSa | < missing string >

A → aAbb | aBbb B → ccc

Provide the missing string as a single line in the given text file (e.g., if your response is xSSy, submit a file with a single line containing string "xSSy" (of course, without the quotes)).

• (3 marks) [E2-Qc2.txt] Does there exist a regular expression, DFA, regular grammar or PDA over the alphabet Σ = a, b, c which is equivalent to the language L? (Answer the following question as a string of bits that translate to 1 for yes and 0 for no. For example, if your answer is “no, no, yes, no" give your response as 0010).

Exercise 3: Automata........ 25 marks

• Answer the following questions based on the finite state automaton M1 present in the JFLAP file

FA-3.a.jK available in Assessments section of the course website. Assume alphabet Σ = {a, b, c, d, e, f }.

1. (2 marks) [E3-Qa1.txt] Give four strings of length 4 accepted by M1. Please type each string on a new

2. (2 marks) [E3-Qa2.txt] Give four strings of length 4 rejected by M1. Please type each string on a new

• (4 marks) [E3-Qa3.txt] Give the language of this machine M1 as a regular

4. (2 marks) [E3-Qa4.jff] Remove any redundant states from M1 and adjust the transitions Give your answer as a .jff JFLAP file.

• (4 marks) [E3-Qa5.jff] Create an automaton M2 (deterministic or non-deterministic) such that it accepts the language L1 where L1 = L(M1) L (aca + aba + bab)∗ (a(ba)∗ + c∗a) . Your machine should not accept words that are not in this Give your answer in a .jff JFLAP file.

• Let L1 = {w | w ∈ {0, 1}∗, w does not contain the substring 101101}.

  1. (4 marks) [E3-Qb1.jff] Give the DFA M3 where L(M3) = L1.

  2. (3 marks) [E3-Qb2.txt] Give the regular expression R such that L(R) = L1.

Notation x, A/X  means a transition where x is the input symbol being read, A is the symbol on top of the stack that is popped, and X  is the symbol pushed onto the stack. Here, λ stands for the “empty” input and g stands for the “empty” stack symbol. Acceptance is by final state and empty stack.

1. (2 marks) [E3-Qc1.txt] Give 4 strings of length 11 over Σ that are accepted by PDA M4. Remember to type each string on a new

2. (2 marks) [E3-Qc2.txt] Give 4 strings of length 11 over Σ that are rejected by PDA M4. Remember to type each string on a new

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