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).
(2 marks) [E1-Qa1.txt] Give two non-empty words w1 and w2 such that {w1, w2} ⊆ L(R1) ∩ L(R2).
(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).
(1 mark) [E1-Qa4.txt] Give a non-empty word w ∈ L(R1) such that w wr ∈ L(R1).
(1 mark) [E1-Qa5.txt] Give a non-empty word w ∈ L(R1) such that w wr g L(R1).
(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.
(2 marks) [E1-Qb1.txt] L1 = {a3n+2bm+1 | n ≥ 1, m ≥ 0, m mod 2 = 1}.
(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.
(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
(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
(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).
(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
(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}.
(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 }.
(2 marks) [E3-Qa1.txt] Give four strings of length 4 accepted by M1. Please type each string on a new
(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
(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}.
(4 marks) [E3-Qb1.jff] Give the DFA M3 where L(M3) = L1.
(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.
(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 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
DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma
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. Thisprogram will have two classes, a LineItem class and a Transaction class. Th
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
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
| Sun | Mon | Tue | Wed | Thu | Fri | Sat |
|---|---|---|---|---|---|---|
30 | 31 | 1 | 2 | 3 | 4 | 5 |
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 1 | 2 | 3 |
