(10 pt) Design CFGs for the given languages: (a) (4 pt) Write a grammar that des

Question

(10 pt) Design CFGs for the given languages: (a) (4 pt) Write a grammar that describes the strings 0T1T where m>n. (b) (6 pt) Write a grammar that describes a "baby language" and list two most interesting sentences he/she will say: the baby has very limited vocabularies "apple" "puppy" "ow "eat" "mama" "baba" "big" red" the baby knows a few basic rules to put together a sentence: (1) a sentence can be a noun, a verb or an adjective (2) a sentence can consist of a verb and one or more noun(s) (adjectives are optional), where a noun should be before the verb and/or after the verb, (3) an adjective only can be immediately before the noun.

Explanation / Answer

(a)
S -> 0S1 | A
A -> 1A | 1

Explanation

S is for having equal number of 0's and 1's

A is for having 1/more 1's

(b)

S -> one | two | three

one -> noun | verb | adjective
two -> verb two1
two1 -> noun verb two1 | verb noun two1 | verb noun verb two1 | epsilon
three -> adjective noun

noun -> apple | puppy | owl | baba | red
verb -> eat
adjective -> big

Explanation

one, two and three are for the points 1, 2 and 3 given respectively

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.