这个作业是完成编译原理相关的习题

comp2022 Assignment 4

Problem 1. Let Σ = {a, b} and consider the language L1 ⊆ Σ

∗ of all strings of

the form a

mu where m ≥ 0 and u has at most m many as in it. Thus, e.g., aababa

and aabba and aa are in L1, but aababaabb is not in L1.

1. Give a context-free grammar G1 = (V, Σ, R, S) that recognises the language L1.

2. Explain why your grammar is correct.

3. Explain whether or not L1 is regular.

Problem 2. In this problem you will design a context-free grammar that generates

the language associated with a non-negative integer counter. Let Σ = {p, m}. We

say that a string w ∈ Σ

∗

is a valid counter string if, when read from left to right, and

interpreting p as adding 1 and m as subtracting 1, and we start from 0, the running

sum is non-negative. For instance, ppm and pm and ppmmp are valid counter strings,

but pmmp and mpp are not valid counter string.

1. Give a context-free grammar G2 = (V, Σ, R, S) that recognises the language L2

of valid counter strings.

2. Explain why your grammar is correct.

3. Explain whether or not L2 is regular.

Problem 3. In this problem you will implement the CYK algorithm and extend

it to provide rightmost-derivations and detect ambiguous strings. Your algorithm will

have three modes: membership, rightmost-derivation, and ambiguous. Input is read

from standard input (stdin). The first line of input indicates which mode is to be

executed. The remaining input is the data to act on. Examples of usage, and of input

and output are provided in Appendix B.

1. Membership mode

• Input: membership followed by a context-free grammar in Chomsky normalform followed by a sequence of input strings.

• Output: One line per input string, giving the string, a comma, and then 1

if the string is generated by the grammar and 0 otherwise.

2. Rightmost-derivation mode

• Input: rightmost-derivation followed by a context-free grammar in

Chomsky normal-form followed by an input string that is generated by the

context-free grammar.

• Output: A sequence of lines, each line containing the next step of a rightmost

derivation of the input string.

3. Ambiguous mode

• Input: ambiguous followed by a context-free grammar in Chomsky normalform followed by a sequence of input strings.

• Output: One line per input string, giving the string, a comma, and then 1

if the string is ambiguous and 0 otherwise

**程序辅导定制C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB**

本网站支持 Alipay WeChatPay PayPal等支付方式

**E-mail:** vipdue@outlook.com **微信号:**vipnxx

如果您使用手机请先保存二维码，微信识别。如果用电脑，直接掏出手机果断扫描。