COSC1107/1105 - Computing Theory Assignment 1 (10%) Total marks: 75 Deadline: Sunday March 26th 2017, 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 first") 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. Remember 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 will need to submit all your files inside a .zip file via this Google Form: http://tinyurl.com/ct17-ass1-sub • Answers to questions must be submitted in individual text or JFLAP files. The exact file names for all files must be used (including exact capitalization and file extension), as indicated in each question. All such files must be put inside a single zip file called -CT17A1.zip. For example, 3234212-CT17A1.zip In total, this zip file should contain 28 .txt and 3 .jff files. • Place all files in the root of the zip file; do not place the files in a folder inside your submission file. • Files with extension .txt must be text files (not Word or any other binary version). If in doubt, please check the type of your files, for example using file command in Unix-based systems. • When requested to submit a file with one or more words/strings (e.g., regexp or words), you should submit a file 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 a line "w1=abc", but just "abc" without quotes). • When requested to submit a file with a binary yes/no or true/false answer, you should submit a file with a single 1 or 0, and nothing else (except in the case of Question 2.c(ii), where a string of 1's and 0's is required). • When asked to submit a ".jff" file, it should be in proper JFLAP format. Your JFLAP files must run error-free in version 7 of JFLAP. It is your responsibility to test your files in JFLAP 7 before submitting. Submissions not compatible with these instructions will attract zero marks and do not warrant a re-submission. Corrections: From time to time, students or staff find errors (e.g., typos or wrong symbols) in the assignment specification. 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 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 clarification, 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. 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, symbol + denotes the alternation/choice operator equivalent to j. For the purpose of this assignment, we will follow JFLAP and use operator + to denote an alternation. Silence Policy: A silence policy will take effect 48 hours before this assignment is due. This means that no questions about this assignment will be answered, whether they are asked on the discussion board, by email, or in person. 1COSC1107/1105 - Computing Theory Assignment 1 Page 2 of 4 Exercise 1: Regular Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 marks For parts (a) to (c), 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 = (a + b∗)cc∗a∗(c + b∗)∗ and R2 = (a + b)∗c∗c(a∗ + b)∗ be two regular expressions. i. (2 marks) [E1-Qa1.txt] Give two non-empty words w1 and w2 such that fw1; w2g ⊆ L(R1) \ L(R2). ii. (2 marks) [E1-Qa2.txt] Give two non-empty words w1 and w2 such that fw1; w2g ⊆ L(R1) n L(R2). iii. (2 marks) [E1-Qa3.txt] Give two non-empty words w1 and w2 such that fw1; w2g ⊆ L(R2) n L(R1). iv. (1 mark) [E1-Qa4.txt] Give a non-empty word w 2 L(R1) such that w · wr 2 L(R1). v. (1 mark) [E1-Qa5.txt] Give a non-empty word w 2 L(R1) such that w · wr 62 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 = fanb4m+3 j n ≥ 1; m ≥ 0; (n + 1) mod 2 = 0g. ii. (2 marks) [E1-Qb2.txt] L2 = L1, where L stands for the complement of L; we assume alphabet Σ = fa; bg. iii. (2 marks) [E1-Qb3.txt] L = fw j w 2 fa; bg∗; jwj mod 4 = 0g, where jwj denotes the length of word w. iv. (2 marks) [E1-Qb4.txt] L = fanw1 j n > 0; w1 2 ((fa; bg∗ n fa; cg∗) [ fcg)g \ fw2b j w2 2 fa; cg∗g. v. (3 marks) [E1-Qb5.txt] L = fw j w 2 f0; 1g∗; w does not contain the substring 110110g. (c) Let R1 and R2 be two regular expressions over a non-empty alphabet Σ. Answer true or false by placing a 1 for true and a 0 for false in a text file as you have for the previous questions. i. (2 marks) [E1-Qc1.txt] If we assume that L(R1) ⊂ L(R2), then it is the case that L(R1 ∗) ⊆ L(R2 ∗). ii. (2 marks) [E1-Qc2.txt] Given the above, is the following statement true? If L(R1 ∗) ⊂ L(R2 ∗), then L(R1) ⊆ L(R2). Exercise 2: Grammars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 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 ! AbB A ! Aab j  B ! Bbc j Bab j C C ! Ca j Cc j  ii. (3 marks) [E2-Qa2.txt] Give a regular expression R such that L(R) = L(G2), where G2 is: S ! AbBCS j  A ! Ac j Aa j  B ! Ba j Bb j a j b C ! Ca j Cb j Cc j  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). Version: March 10, 2017 Exercise 2 continues on the next page. . .COSC1107/1105 - Computing Theory Assignment 1 Page 3 of 4 (b) Let G3 = (fSg; fa; bg; Γ; S) be a grammar, where the set of rules Γ is defined as follows: S ! SabbS S ! SbabS S ! SbbaS S !  i. (3 marks) [E2-Qb1.txt] Is G3 an ambiguous grammar? Give your answer as 1 for yes, 0 for false. ii. (3 marks) [E2-Qb2.txt] Is there a relationship between the number of as and bs in L(G3)? Give your answer as 1 for yes, 0 for no. iii. (4 marks) [E2-Qb3.txt] Does there exist a regular expression R such that L(R) = L(G3)? If it exists, provide such R; otherwise, simply put 0. (c) Given the language L = fanb3m+1a3c2mbn j n; m > 0g. i. (3 marks) [E2-Qc1.txt] Complete the following context-free grammar G such such L(G) = L. S ! aSb j < missing string > A ! bbbAcc j bbbBcc B ! aaa Provide the missing string as a single line in the given text file (e.g., if your response is xSSy, submit a file with the single line xSSy). ii. (3 marks) [E2-Qc2.txt] Does there exist a regular expression, DFA, regular grammar or PDA over the alphabet Σ = fa; b; cg 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 marks (a) Answer the following questions based on the finite state automaton M1 present in the JFLAP file FA-3.a.jff available in Assessments section of the course website. i. (2 marks) [E3-Qa1.txt] Give four strings of length 4 accepted by M1. Please type each string on a new line. ii. (2 marks) [E3-Qa2.txt] Give four strings of length 4 rejected by M1. Please type each string on a new line. iii. (4 marks) [E3-Qa3.txt] Give the language of this machine M1 as a regular expression. iv. (2 marks) [E3-Qa4.jff] Remove any redundant states from M1 and adjust the transitions accordingly. Give your answer as a .jff JFLAP file. v. (4 marks) [E3-Qa5.jff] Create an automaton M2 (deterministic or non-deterministic) such that it accepts the language L where L = L(M1) \ L((b + a)∗(a + bad + bba + fba)∗eba). Your machine should not accept words that are not in this language. Give you answer in a .jff JFLAP file. Version: March 10, 2017 Exercise 3 continues on the next page. . .COSC1107/1105 - Computing Theory Assignment 1 Page 4 of 4 (b) Consider the pushdown automaton M3 over the alphabet Σ = fa; b; cg as shown below. q0 q1 q2 q3 a; =A λ b; =B b; =B c; B= λ a; B=; b; A= PDA M3 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. The symbol  stands for the "empty" string. Acceptance is by final state and empty stack. i. (2 marks) [E3-Qb1.txt] Give 4 strings of length 6 over Σ that are accepted by PDA M3. Remember to type each string on a new line. ii. (2 marks) [E3-Qb2.txt] Give 4 strings of length 6 over Σ that are rejected by PDA M3. Remember to type each string on a new line. iii. (4 marks) [E3-Qb3.jff] It is a well known result that every PDA with acceptance condition of an empty stack and reachability of a final state can be transformed to an equivalent PDA with acceptance condition requiring only reachability of a final state. Transform PDA M3 to an equivalent PDA with acceptance requiring only reachability of a final state. End of assignment paper Question Points Regular Expressions 27 Grammars 26 Automata 22 Total: 75 Version: March 10, 2017