Computing Theory Assignment. Regex, automataCOSC1107/1105 Computing Theory - Assignment 1 -...

Question

Computing Theory Assignment. Regex, automata

COSC1107/1105 Computing Theory - Assignment 1 - Deadline: Sunday August 18th 2019, 11:59 PM COSC1107/1105 - Computing Theory Assignment 1 (10%) Total marks: 75 Deadline: Sunday August 18th 2019, 11:59 PM Please read all the following information before attempting your assignment. This is an individual assignment. You may not collude with any other individual, or plagiarise their work. Students are expected to present the results of their own thinking and writing. Never copy another student’s work (even if they “explain it to you �rst") and never give your written work to others. Keep any conversation high-level and never show your solution to others. Never copy from the web or any other resource. You are meant to generate the solution to the questions by yourself. Suspected collusion or plagiarism will be dealt with according to RMIT policy. Submission Instructions • You are to submit all your �les inside a .zip �le and & certify your submission using this Google Form: http://tinyurl.com/ct19-ass1-sub • Answers to questions must be submitted in individual text or JFLAP �les. The exact �le names for all �les must be used (including exact capitalization and �le extension), as indicated in each question. All such �les must be put inside a single zip �le called .zip. For example, 3234212.zip In total, this zip �le should contain 25 .txt and 5 .jff �les. • Place all �les in the root of the zip �le; do not place the �les in a folder inside your submission �le. • Files with extension .txt must be text ASCII/UTF-8 �les (not Word or any other format). If in doubt, please check the type of your �les, for example using file command in Unix-based systems. Con�rm it is in ASCII or UTF-8 format, and not in other formats like Little-endian UTF-16 or Rich Text Format. • When requested to submit a �le with one or more words/strings (e.g., regexp or words), you should submit a �le with each string on a new line, and nothing else. Do not include your name, quotes, dummy lines, or any other information or character (e.g., do not type “w1=abc”, but just “abc” without quotes). • When asked to submit a “.jff” �le, it should be in proper JFLAP format. Your JFLAP �les must run error- free in version 7 of JFLAP. It is your responsibility to test your �les in JFLAP 7 before submitting. • Question 5 is a bonus question. You can still get full marks without answering this question. Submissions not compatible with these instructions will attract zero marks and do not warrant a re-submission. Corrections: From time to time, students or sta� �nd errors in the assignment speci�cation. In that case, a corrected version will be uploaded to the course web page as quickly as possible, an announcement will be made on the course web page as well as in the forum. Check the version date on the bottom left. Forum postings on assignment: Never post any information on the forum that may disclose how to solve a question or what the solution may be. You may only post assignment related questions for clari�cation, for example, to clarify certain notation. Any post discussing possible solutions or strategies may directly be considered plagiarism, see above. If in doubt, do not post and ask your tutor the question instead. Silence Policy: A silence policy will take e�ect 48hrs before this assignment is due. This means no questions about this assignment will be answered, whether they are asked on the discussion board, by email, or in person. Late Submissions/Extensions: A penalty of 10% per day is applied to late submissions up to 5 days, after which you will lose ALL the assignment marks. Extensions will be given only in exceptional cases; please refer to Special Consideration process. Special Considerations given after solutions have been released (between 1 and 2 weeks after deadline) will automatically result in an equivalent assessment in the form of a test, assessing the same knowledge and skills of the assignment (location and time to be arranged by the instructor). 1 http://tinyurl.com/ct19-ass1-sub https://www.rmit.edu.au/students/student-essentials/assessment-and-exams/assessment/special-consideration COSC1107/1105 - Computing Theory Assignment 1 Page 2 of 5 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 ϵ to denote the empty string (see Preferences menu). For parts (i) to (iii), please type each word on a new line. The notation wi ·w j denotes concatenation of words wi and w j , 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 di�erent if more than one). i. (2 marks) [E1-Qa1.txt] Give two non-empty words w1 and w2 such that {w1,w2} ⊆ L(R1) ∩ L(R2). ii. (2 marks) [E1-Qa2.txt] Give two non-empty words w1 and w2 such that {w1,w2} ⊆ L(R1) \ L(R2). iii. (2 marks) [E1-Qa3.txt] Give two non-empty words w1 and w2 such that {w1,w2} ⊆ L(R2) \ L(R1). iv. (1 mark) [E1-Qa4.txt] Give a non-empty word w ∈ L(R1) such that w ·wr ∈ L(R1). v. (1 mark) [E1-Qa5.txt] Give a non-empty word w ∈ L(R1) such that w ·wr < l(r1).="" vi.="" (1="" mark)="" [e1-qa6.txt]="" give="" a="" regular="" expression="" r="" such="" that="" l(r)="L(R1)" ∪="" l(r2).="" vii.="" (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.="" i.="" (2="" marks)="" [e1-qb1.txt]="" l1="{a3n+2bm+1" |="" n="" ≥="" 1,m="" ≥="" 0,m="" mod="" 2="1}." ii.="" (2="" marks)="" [e1-qb2.txt]="" l2="L1," where="" l="" is="" the="" complement="" of="" l="" (assume="" alphabet="" σ="{a,b})." iii.="" (2="" marks)="" [e1-qb3.txt]="" l="{w" |="" w="" ∈{a,b}∗,="" |w="" |="" mod="" 3="2}," where="" |w="" |="" denotes="" the="" length="" of="" w="" .="" iv.="" (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 (a) Provide regular expressions for the following languages. i. (3 marks) [E2-Qa1.txt] Give a regular expression R such that L(R) = L(G1), where G1 is: S → AcB A→ ac | bC | ϵ B → baB | caB | D C → bC | ϵ D → aD | b ii. (3 marks) [E2-Qa2.txt] Give a regular expression R such that L(R) = L(G2), where G2 is: S → ACS | ϵ A→ aA | bA | bB B → cB | ϵ C → bcC | acC | D D → bD | ϵ iii. (2 marks) [E2-Qa3.txt] Give a regular expression R such that L(R) = L(G1) ∪ L(G2). iv. (2 marks) [E2-Qa4.txt] Give a regular expression R such that L(R) = L(G1) ∩ L(G2). (b) Let G3 = ({S}, {a,b}, Γ, S) be a grammar, where the set of rules Γ is de�ned as follows: S → aSbSa S → bSbSa S → aSbSb S → ϵ i. (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. Version: August 6, 2019 Exercise 2 continues on the next page. . . COSC1107/1105 - Computing Theory Assignment 1 Page 3 of 5 (c) Let L = {c2n−1amc3b2m+1an | n,m > 0}. i. (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 �le (e.g., if your response is xSSy, submit a �le with a single line containing string "xSSy" (of course, without the quotes)). ii. (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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

assignment1-cosc1107-1105-ct19-xc4svfnd.pdf

Sudipta · Accepted Answer

18357/E1-Qa1.txt
R1 = 1(1*+2*)3*(2*+3)1*2(1+3)*2*
R2 = 1*3(2+3)*2*(1+3)*(1+3)*
{w1,w2}⊆ L(R1)∩L(R2)
From R1 take 1,3,2 as * denotes that we can take 0 or more values and + denotes combination of either of the values which means:
say for (1*+2*), if we take only 1 and we can neglect 2* or we can take 2 and avoid 1* or we can neglect both or any combination of 1 and 2
So, L(R1)=132, 133
	L(R2)=132, 133
which gives two non empty intersection
132
133
18357/E1-Qa2.txt
R1 = 1(1*+2*)3*(2*+3)1*2(1+3)*2*
R2 = 1*3(2+3)*2*(1+3)*(1+3)*
{w1,w2} L(R1)\L(R2)
First divide R1 with R2 then you will get a regular expression, which means set of all words which belong to L(R1) but not L(R2).
From this regular expression we can get two strings as w1 and w2.
for the above R1 and R2 derived regular expression is 1(1*+2*)3*(2*+3)1*2(1+3)* after division.
So, w1=1123231
	w2=121322121
1123231
121322121
18357/E1-Qa3.txt
R1 = 1(1*+2*)3*(2*+3)1*2(1+3)*2*
R2 = 1*3(2+3)*2*(1+3)*(1+3)*
L(R2)/L(R1)
First divide R2 with each element of R1 then take union of each. You will get a regular expression.
From this regular expression we can get two strings as w1 and w2.
for the above R1 and R2 derived regular expression is 1*3(2+3)*2*(1+3)*(1+3)* after division.
So, w1=3
	w2=13
3
13
18357/E1-Qa4.txt
R1 = 1(1*+2*)3*(2*+3)1*2(1+3)*2*
R2 = 1*3(2+3)*2*(1+3)*(1+3)*
from L(R1) take 123 as * denotes that we can take 0 or more values and + denotes combination of either of the values which means:
we take 1 then we take 2 from (1*+2*) and 3 from 3* so w =123. Similarly, we can get 321 from (2*+3)1*2(1+3)*2* that is reverse of w.
So, w along with w reverse belongs to L(R1) which is 123321.
Alternately we can have w=121 also.
123
18357/E1-Qa5.txt
R1 = 1(1*+2*)3*(2*+3)1*2(1+3)*2*
R2 = 1*3(2+3)*2*(1+3)*(1+3)*
From R1 take 1 then from (1*+2*) take null,from 3* take 3, from (2*+3) take null, from 1* take null,
from 2 take 2, from (1+3)* take 3 and from 2* take null. Hence w is 1323.
So, w along with w reverse doesnot belongs to L(R1) which is 13233231.
Alternately we can have w=1323 also.

COSC1107/1105 Computing Theory - Assignment 1 - Deadline: Sunday August 18th 2019, 11:59 PM COSC1107/1105 - Computing Theory Assignment 1 (10%) Total marks: 75 Deadline: Sunday August 18th 2019, 11:59...

Answer To: COSC1107/1105 Computing Theory - Assignment 1 - Deadline: Sunday August 18th 2019, 11:59 PM...

Answer To This Question Is Available To Download

Related Questions & Answers

Submit New Assignment