This homework is about context-free grammars and parsing. All answers must be ty

Question

This homework is about context-free grammars and parsing. All answers must be typed. No handwriting will be accepted. 1. Give a context-free grammar (CFG) for each of the following languages over the alphabet (a.b (a) All nonempty strings that start and end with the same symbol. (b) All strings with more a's than b's. (c) All palindromes (a palindrome is a string that reads the same forwards and backwards). 2. A production (grammar rule) in BNF has the form: where A is a nonterminal, X. (iz 1, , m, m > 0) are grammar symbols. Write a context free grammar for the language of productions in BNF. You can assume that each nonterminal is a single uppercase letter and each terminal is a single lowercase letter. You can use--> for .

Explanation / Answer

Answer:

1.a)

S -> aAa | bAb |a | b

A -> aA | bA | epsilon

{S, A} are Non-terminals, {a, b, epsilon} are terminals

1.b)

S -> Aa | BS | SBA

A -> Aa | epsilon

B -> BB | aBb | bBa | epsilon

1.c)

S -> aSa | bSb | a | b | epsilon

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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