Reference no: EM132360945

Computing Theory Assignment -

Exercise 1: Regular Expressions

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 j. For the purpose of this assignment, we follow JFLAP and use operator + to denote an alternation. In JFLAP, you can use λ or ∈ to denote the empty string (see Preferences menu).

For parts (i) to (iii), please type each word on a new line. The notation w_i · w_j denotes concatenation of words w_i and w_j, and w^r denotes the word obtained by reversing w.

(a) Let R₁ = 1(1*+2*)3*(2*+3)1*2(1+3)*2* and R₂ = 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).

i. Give two non-empty words w₁ and w₂ such that {w₁, w₂} ⊆ L(R₁) ∩ L(R₂).

ii. Give two non-empty words w₁ and w₂ such that {w₁, w₂} ⊆ L(R₁) \ L(R₂).

iii. Give two non-empty words w₁ and w₂ such that {w₁, w₂} ⊆ L(R₂) \ L(R₁).

iv. Give a non-empty word w ∈ L(R₁) such that w · w^r ∈ L(R₁).

v. Give a non-empty word w ∈ L(R₁) such that w · w^r ∉ L(R₁).

vi. Give a regular expression R such that L(R) = L(R₁) ∪ L(R₂).

vii. Give a regular expression R such that L(R) = L(R₁) ∩ L(R₂).

(b) Give regular expressions for the following languages.

i. L₁ = {a³ⁿ⁺²b^m+1|n ≥ 1, m ≥ 0, m mod 2 = 1}.

ii. L₂ = L₁^-, where L is the complement of L (assume alphabet ∑ = {a, b}).

iii. L = {w|w ∈ {a, b}*, |w| mod 3 = 2}, where |w| denotes the length of w.

iv. L = {bⁿw₁|n > 1, w₁ ∈ (({a, c}* ∩ {a, b, c}*)\({b}*∪ {c}))} ∩ {w₂c|w₂ ∈ {a, b ,c}*}.

Exercise 2: Grammars

(a) Provide regular expressions for the following languages.

i. Give a regular expression R such that L(R) = L(G₁), where G₁ is:

S → AcB

A → ac | bC | ∈

B → baB | caB | D

C → bC | ∈

D → aD | b

ii. Give a regular expression R such that L(R) = L(G₂), where G₂ is:

S → ACS | ∈

A → aA | bA | bB

B → cB | ∈

C → bcC | acC | D

D → bD | ∈

iii. Give a regular expression R such that L(R) = L(G₁) ∪ L(G₂).

iv. Give a regular expression R such that L(R) = L(G₁) ∩ L(G₂).

(b) 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 → ∈

i. Does there exist a regular expression R such that L(R) = L(G₃)? If it exists, provide such R; otherwise, simply put 0.

(c) Let L = {c^2n-1a^mc³b^2m+1aⁿ|n, m > 0}.

i. Complete the following context-free grammar G 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)).

ii. 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

(a) Answer the following questions based on the finite state automaton M₁ present in the JFLAP file FA-3.a.j available in Assessments section of the course website. Assume alphabet ∑ = {a, b, c, d, e, f}.

i. Give four strings of length 4 accepted by M₁. Please type each string on a new line.

ii. Give four strings of length 4 rejected by M₁. Please type each string on a new line.

iii. Give the language of this machine M₁ as a regular expression.

iv. Remove any redundant states from M₁ and adjust the transitions accordingly. Give your answer as a .jff JFLAP file.

v. Create an automaton M₂ (deterministic or non-deterministic) such that it accepts the language L₁ where L₁ = L(M₁) ∩ L((aca + aba + bab)*(a(ba)*+ c*a)). Your machine should not accept words that are not in this language. Give your answer in a .jff JFLAP file.

(b) Let L₁ = {w|w ∈ (0, 1)*, w does not contain the substring 101101}.

i. Give the DFA M₃ where L(M₃) = L₁.

ii. Give the regular expression R such that L(R) = L₁.

(c) Consider the pushdown automaton M₄ over the alphabet = (a, b, c} as shown below.

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 ∈ stands for the "empty" stack symbol. Acceptance is by final state and empty stack.

i. Give 4 strings of length 11 over ∑ that are accepted by PDA M₄. Remember to type each string on a new line.

ii. Give 4 strings of length 11 over ∑ that are rejected by PDA M₄. Remember to type each string on a new line.

Exercise 4: Telephone System Design

Answer the following questions by submitting a JFLAP file for each.

(a) You have been tasked to design part of the internal phone system for a company that is expanding its operations from Melbourne to include a new Sydney office. Someone else in you're the team will handle the internal routing of the calls; your job is to design a deterministic finite state machine that takes a number as input and determines whether it is valid (or should be rejected). The input to the system is a string composed in the following way:

• The first part is optional and carries the area code of the office you want to be connected to: Melbourne is 03 and Syndey is 02.
• The next 2 digits are 94 (regardless of the city).
• The next 3 digits determine the department you want to be connected to: Marketing is 555, R&D is 528 and Sales is 552.
• The final three (meaningful) digits indicate the personal extension of whoever you are calling: Extensions are all in the range 000-059.

Besides the above format for numbers, your automaton must adhere to the following rules:

• As with all phone numbers, you should be able to enter any digits after the personal extension digits and still be connected, however you must end your string with a # symbol to tell the system the input is complete; otherwise the whole number is deemed invalid.
• The area code is also optional. If you are in Melbourne, you should not have to dial 03 to connect to the Melbourne office, so your automaton should accept numbers with an area code and numbers without an area code. For example, to be connected to extension 029 in the Melbourne sales department you would dial 0394552029#. However, 94552029#, 0394552029123456# and 94552029123456# should also be accepted.
• Finally, as the Sydney office is just being set up, they do not have an R&D department yet, any phone call directed explicitly to the Sydney R&D apartment should also be rejected. If there is no area code you do not need to worry about this.

Any number that does not fit the pattern, as explained above, is invalid (and should be rejected).

(b) Several months later your company is again contracted to make some modifications to the system. This time they want exactly the same functionality, however now they would like the user to be able to enter their customer number after the # symbol. The only catch is that the customer numbers have been designed by an ex-Computing Theory student and are needlessly complicated! The numbers are split up into two parts of equal length; with the first part being composed of the digits 0-4 and the second part composed of the digits 5-9. These parts can be any length, but they must be of equal size (and they must exist!). The rest of the machine should function exactly as before. The company asked you for the simplest type of automaton possible as they want to save money. Remember that whenever we use PDAs, the acceptance condition used is both final state and empty stack.

To use a similar example as before, if your customer number was 123678 and you wanted to be connected to extension 029 in the Melbourne sales department you would dial 0394552029#123678. However, 94552029#123678, 0394552029123456#123678 and 94552029123456#123678 should also be accepted.

Exercise 5: Intersection of Regular Languages

Find the regular expression R₃ such that L(R₃) = L(R₁) ∩ L(R₂), where:

R₁ = (ca)*a(c + b)*(ab + ca)*; and

R2 = ((b + c)*a(c + a)(c + a)*(c + a + b)*)*.

Attachment:- Computing Theory Assignment Files.rar