I need help with the following question. 1. (18 points) Let: a) Give CFGs for Li

Question

I need help with the following question.

1. (18 points) Let: a) Give CFGs for Li and L2 b) Is LL2 a CFL? Justify your answer. c) Using the CFG designed for Li as a template, design another CFG for the language (denoted as Lpre of all strings that are prefixes of the strings in L.e Lpref = {x | x is a prefix of a string in Li} Note, by this definition, each string in L will generate multiple strings in Lpref. For example, the string abbcc which is in L will generate the following list of strings in Lgref: e, a, ab, abb, abbe, abbec

Explanation / Answer

1.

Grammar for L1

S -> AC
A -> aAbb | abb
C -> cC | c

Grammar for L2

S -> AB
A -> aA | a
B -> bBcc | bcc

Note: One question at a time please -- Policy of Chegg

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---