Definition For the context free language defined as follows: sigma = {a, b} Nont

Question

Definition For the context free language defined as follows: sigma = {a, b} Nonterminals: S, A, C, X Production rules: a. S - > A X C b.X - > A X C | A c. A - > a d. C - > ab | ba Request: True or False for the items listed below. a. A is a string in this language (see context free language above). b. Using the definition from (a), aaa is a string in this language. c. Using the definition from (a), A X C is a string in this language. d. Using the definition from (a), every string in this language has twice as many a's as b's.

Explanation / Answer

Let's look at each of the 4 questions
a. None of the non terminals are producing empty string. So, this is FALSE.
-----
b. The starting symbol is S
S -> A X C
and C ends with ab or ba. So, the string has to contain at least one b.
So, we cannot generate the string aaa.
FALSE
-----
c.
AXC are non terminals. So they can't be strings. They generate strings.
Therefore, this is FALSE.
-----
d.
Consider the following derivation:
S -> AXC
-> AAC
-> aa C
-> aa ab

In this string we have 3 a's and 1 b. So, we do not have twice as many a's as the number of b's in every string.
Therefore, this is also FALSE.

------------

If helpful, please click on the thumbs up button. Thank you.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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