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
CS 340 Milestone One Guidelines and Rubric Overview: For this assignment, you will implement the fundamental operations of create, read, update,
Retail Transaction Programming Project Project Requirements: Develop a program to emulate a purchase transaction at a retail store. This
7COM1028 Secure Systems Programming Referral Coursework: Secure
Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip
CS 340 Final Project Guidelines and Rubric Overview The final project will encompass developing a web service using a software stack and impleme
