Language Processor (Regex, Grammar And Dfas And Nfas )

Part II: Grammars Submission: On Canvas, under Assignments Deadline: Week 5, Thurs 16th Feb 2023 Notes on answering this question: - Pay attention to what kind of grammar I ask for (regular, or context free, or some other type). - For instance: if I ask for a regular grammar and you give me some other kind of grammar, then you may lose marks! - In particular, if your regular grammar contains a rule of the form S⟶abγ or S⟶D or S⟶εD, then this is not a regular grammar and your answer contains an error. - Always clearly specify the start symbol. - The alphabet (set of tokens) of a language cannot contain ε. ε is the empty string, that is, an absence of tokens. If your answer contains something of the form T={ε,…} (where T is supposed to be a set of tokens for your language) — then your answer is probably wrong and you’re probably losing marks. Some of you have not met set notation before, so here’s a quick tutorial: - The language determined by the regex /a*/ is { aⁿ | n ∈ ℕ} or equivalently { aⁿ | n ∈ {0,1,2,…} } or equivalently { aⁿ | n ≥ 0 }. - The language determined by the regex /(a|b)?/ is { a, b, ε }. - The language determined by the regex /a+b+/ is { aᵐbⁿ | m,n ≥ 1 } or equivalently { aᵐbⁿ | m ≥ 1, n ≥ 1 } or equivalently { aᵐbⁿ | m,n ∈ {1,2,3,…} }. - The language determined by the English description “any nonzero digit” is { 1, 2, 3, 4, 5, 6, 7, 8, 9} or equivalently { 1, 2, … , 9} or equivalently { n | 9 ≥ n ≥ 1 } or equivalently { n | 0 < n ≤ 9 }. Now on to the questions: 1. Write the language determined by the regex /a*b*/ 2. Write a regular grammar to generate the language determined by the regex /a*b*/ 3. Write the language determined by the regex /(ab)*/ 4. Write a regular grammar to generate the language determined by the regex /(ab)*/ 5. Write the language determined by /Whiske?y/. The alphabet is {W,h,i,s,k,e,y} (W is a terminal symbol here). 6. Write a regular grammar to generate the language matched by /Whiske?y/ 7. Write a regular grammar to generate decimal numbers; the relevant regex is /[1-9][0-9]*(\.[0-9]*[1-9])?/. You may find it useful to use notation resembling D ::= 0 | 1 | … | 9 to denote an set of ten production rules. 8. Give a context free grammar for the language L = { aⁿ bⁿ | n ∈ ℕ}. 9. Give a context free grammar for the set of properly bracketed sentences over alphabet { 0 , ( , ) }. So 0 and ((0)) are fine, and 00 and 0) are not fine. 10. Write a context free grammar to generate possibly bracketed expressions of arithmetic with + and * and single digit numbers. So 0 and (0) and 0+1+2 and (0+9) are fine, and (0+)1 and 12 are not fine. 11. Give a grammar for palindromes over the alphabet { a , b }. 12. A parity-sequence is a sequence consisting of 0s and 1s that has an even number of ones. Give a grammar for parity-sequences. 13. Write a grammar for the set of numbers divisible by 4 (base 10; so the alphabet is [0-9]). You might like to read this page on divisibility testing, first. You may use dots notation to represent a sequence, as in for example the sequence Z3,Z6,Z9,…,Z999 to mean “Z followed by some number divisible by three and strictly between 0 and 1000”. 14. Write a grammar for the set of numbers divisible by 3 (base 10; so the alphabet is [0-9]). So for example 0, 003, and 120 should be in your language, and 1, 2, and 5 should not 15. (Unmarked) Write a grammar for the set of numbers divisible by 11 (base 10; so the alphabet is [0-9]). More on Grammars …. 16. State which of the following production rules are left-regular, right- regular, left-recursive, right-recursive, context-free (or more than one, or none, of these): 1. Thsi ⟶ This (a rewrite auto-applied by Microsoft Word). 2. Sentence ⟶ Subject Verb Object. (Here Sentence, Subject, Verb, and Object are non-terminal symbols.) 3. X ⟶ Xa. 4. X ⟶ XaX. 17. What is the object language generated by X⟶Xa (see Lecture 2)? Explain your answer. 18. Construct context-free grammars that generate the following languages: 1. (ab|ba)∗, 2. {(ab)n an| n≥1}, 3. {w∈{a,b}∗ | w is a palindrome} 4. {w∈{a,b}∗ | w contains exactly two bs and any number of as } 5. {an bm| 0≤n≤m≤2n} 19. Consider the grammar G=({S,A,B},{a,b},P,S) with productions S ⟶ SAB | ε A ⟶ aA | ε B ⟶ Bb | ε 1. Give a leftmost derivation for aababba. 2. Draw the derivation tree corresponding to your derivation. 20. State with proof whether the following grammars are ambiguous or unambiguous: 1. G=({S},{a,b},P,S) with productions S ⟶ aSa | aSbSa | ε 2. G=({S},{a,b},P,S) with productions S ⟶ aaSb | abSbS | ε 21. Rewrite the following grammar to eliminate left-recursion: exp ⟶ exp + term ∣ exp – term ∣ term 22. Write a grammar to parse arithmetic expressions (with + and ×) on integers (such as 0, 42, −1). This is a little harder than it first sounds because you will need to write a grammar to generate correctly-formatted positive and negative numbers; a grammar that generates −01 is unacceptable. You may use dots notation to indicate obvious replication of rules, as in “D⟶0∣⋯∣9”, without comment. (Note that a parser is not an evaluator. This question is not asking you to write an evaluator. Also note that the grammar only needs to be unambiguous if the question asks you to provide an unambiguous grammar.) 23. Write two distinct parse trees for 2+3∗4 and explain in intuitive terms the significance of the two different parses to their denotation. Part III: DFAs and NFAs Submission: On Canvas, under Assignments Deadline: Week 7, Fri 3rd March 2023 You may find draw.io useful for drawing automata. If you know of a similar and better tool, please let me know. You can insert images from https://automatonsimuator.com too as long as the edge annotations are clearly shown (note sometimes they are difficult to read). 1. By writing a regular expression or a grammar, describe the language accepted by the DFA 2. By writing a regular expression or a grammar, describe the language accepted by the DFA 3. Construct NFAs (possibly with ϵ-moves) to recognise the languages on alphabet {a,b} such that: 1. L={w∈{a,b}∗ | w contains at most two a’s}. So ϵ and aa and bbbbabba are in L and aaa is not. 2. L={w∈{a,b}∗ | w contains an even number of occurrences of ab as a subword }. So ϵ and a and b and abab and abaaba and baaabab are in L, but ab and ababab and abaabab are not. 3. L={w∈{a,b}∗ | the first and the last letter of w are identical } 4. By writing a regular expression or a grammar, describe the language accepted by the NFA 5. By writing a regular expression or a grammar, describe the language accepted by the NFA 6. (Unmarked) Use the powerset construction (see Lecture 5) to construct a DFA that recognises the same language as the following NFA: 7. (Hard) Let L be the language recognised by the NFA 1. Construct a context-free grammar G that generates language L (a regular grammar is also fine, since every regular grammar is context- free). 2. State with proof whether G is ambiguous or unambiguous. 8. (Unmarked) Let G=({S,A,B},{a,b},P,S) be the context-free grammar with productions: S ⟶ aAbS | bBaS | ε A ⟶ aAbA | ε B ⟶ bBaB | ε Give a short and intuitive English description of the language determined by G (such a description does exist). On PDAs In the questions below, assume the alphabet is {a,b}. Your answer must state the acceptance mode used. In the questions below, the word describe means draw a precise picture of in the style I used in lectures or in the style of this webpage or this pdf, or just search the Internet for how to draw a PDA. 9. Describe a pushdown automaton that recognises {ambnam∣m,n≥0}. 10. Assume m,n≥0. Describe a DFA that recognises { ambnam }. Explain why this question is different from the previous question. 11. Describe a pushdown automaton that recognises {amb2n∣m,n≥0}. 12. Describe a pushdown automaton that recognises {am bn∣m>n>0}. 13. Describe a pushdown automaton that recognises {w∣#aw = #bw}, where #aw is the number of as appearing in w and #b w is the number of bs appearing in w. 14. Describe a pushdown automaton that recognises {w∣#aw = 2#bw }. 15. Describe a pushdown automaton that recognises {w∣#aw ≠ #bw}