1. Homepage
2. Homework
3. Comp2022/2922 A2 - CFLs and non-regularity
This question has been solved

# Comp2022/2922 A2 - CFLs and non-regularity

University of SydneyComp2022Comp2922Models of ComputationCFLs and non-regularity

comp2022/2922 A2 (90 marks) – CFLs and non-regularity s2 2023

• All work must be done individually without consulting anyone else’s solutions in accor- dance with the University’s “Academic Dishonesty and Plagiarism” policies.

• For clarifications and more details on all aspects of this assignment (e.g., level of justifica- tion expected, late penalties, repeated submissions, what to do if you are stuck, etc.) you are expected to regularly monitor the Ed Forum post “Assignment FAQ”.

Problem 1. (10 marks) Fix Σ = {a,b}. For each of the following grammars, provide five strings that are in the language and five strings that are not (you score max(0, 5 num errors) points per part).

1.S aSbb | ε

2. S aA
A
aA | bB

B bB | ε
Problem 2. (10 marks) Consider the following context-free grammar G over

Σ = {a, b}.

S AA
A
AAA | bA | Ab | a

1. Show the grammar is ambiguous by providing two leftmost derivations of the same string.

2. Provide a grammar in Chomsky Normal Form equivalent to G.

Problem 3. (20 marks) Fix Σ = {a,b}. Design context-free grammars for the

following languages:

1. The set of strings of length 6 that have the same number of a and b.

2. The set of strings of the form uvw with u, v, w ∈ {anbn|n Z+}.

3. The set of palindromes whose length is a multiple of 20. Use at most 100 rules.

4. The set of strings not in the set {anb2n+3|n Z+}. 1

comp2022/2922 A2 (90 marks) – CFLs and non-regularity s2 2023

Problem 4. (20 marks) Fix Σ = {a, b}. A string is extreme if its amount of a is more than twice its amount of b plus one, or the other way around. For example, aaaab and babbabbbbba are both extreme, while bbbbbaa and ababab are not.

1. Prove that the set E of extreme strings is not regular (10 marks).

2. Prove that the set P of strings that have an extreme string as a prefix is not regular. Recall that a string x is a prefix of a string y if y = xw for some string w. Thus aaaabbbb is in P (since it has aaaab as a prefix), while ababab is not in P (since no prefix of it is extreme). (10 marks)

Problem 5. (10 marks) Fix Σ = {a, b}. Write a program that takes in a context- free grammar G in CNF and outputs a context-free grammar for the language of strings that are in L(G) and whose number of as is a multiple of 5.

For full marks, your solution should be able to take an arbitrary CNF grammar with 10 variables and output a grammar with at most 100 variables.

Problem 6. (20 marks) You’re honing your skills for the world championship of popular card game Magic: the Gathering. Your goal is to draw through all the cards in your deck, and to this end, you’ve included lots of cards that help you draw more cards. However, if you get unlucky, with some deck orderings you’ve found that this is impossible. You’re interested in determining which deck orderings can be won, and which can’t.

At the start of the game, you draw seven cards from your deck into your hand. The cards in your deck are of the following types:

• Ancestral Recall. When played, you draw three cards.

• Wheel of Fortune. When played, you discard your hand, and then draw seven

cards.

• Cruel Bargain. When played for the first time in a game, you draw four cards. It cannot be played more than once in a game.

• Other, useless cards.

Aside: Unlike in the actual game, you can play any number of cards from your hand in any order, without needing to pay mana.

Your goal is to draw all the cards in your deck, at which point you win. Note that ”overdraw” (drawing more cards than exist in your deck) meets this condition, and so is also a win. We encode a possible ordering of your deck as a string over the alphabet Σ = {a, w, c, x} where a, w, c correspond to the cards starting with those letters, and x corresponds to a useless card. We are interested in the language of strings for which it is possible for you to win.

For example, the following strings are in the language: aax11, wx13, cawx18, awx5wx13

2

comp2022/2922 A2 (90 marks) – CFLs and non-regularity s2 2023

while the following strings are not in the language:
aax12, wx14, cawx19, awx5wx14
Design a context-free grammar for the language described.

• 4 marks will be awarded for cases with strings containing only a, x.

• 4 marks will be awarded for cases with strings containing only a, c, x.

• 4 marks will be awarded for cases with strings containing only w, x.

• 4 marks will be awarded for cases with strings containing only a, w, x.

• The final 4 marks will be awarded for the general case, i.e., for strings over the alphabet a, w, c, x.

## Get in Touch with Our Experts

QQ
WeChat
Whatsapp
University of Sydney代写,Comp2022代写,Comp2922代写,Models of Computation代写,CFLs and non-regularity代写,University of Sydney代编,Comp2022代编,Comp2922代编,Models of Computation代编,CFLs and non-regularity代编,University of Sydney代考,Comp2022代考,Comp2922代考,Models of Computation代考,CFLs and non-regularity代考,University of Sydneyhelp,Comp2022help,Comp2922help,Models of Computationhelp,CFLs and non-regularityhelp,University of Sydney作业代写,Comp2022作业代写,Comp2922作业代写,Models of Computation作业代写,CFLs and non-regularity作业代写,University of Sydney编程代写,Comp2022编程代写,Comp2922编程代写,Models of Computation编程代写,CFLs and non-regularity编程代写,University of Sydneyprogramming help,Comp2022programming help,Comp2922programming help,Models of Computationprogramming help,CFLs and non-regularityprogramming help,University of Sydneyassignment help,Comp2022assignment help,Comp2922assignment help,Models of Computationassignment help,CFLs and non-regularityassignment help,University of Sydneysolution,Comp2022solution,Comp2922solution,Models of Computationsolution,CFLs and non-regularitysolution,