3) Write context-free grammars for the following languages. a) 1 + 0, = {0, 1} c

ID: 3887274 • Letter: 3

Question

3) Write context-free grammars for the following languages.

a) 1+0, = {0, 1}

c) strings with either a’s and/or b’s only, or a’s and/or c’s only, in any order; strings may be of any length, = {a, b, c},

sample strings for part one of the definition: , a, aaa, b, abb, baab, bbabb

d) w*wR, = {a, b, c} where R means reverse

1) Write a RE for all strings that contain '00' or '11' (exclusive or). = {0, 1}

Write a pumping lemma proof that this language is not regular:

{0n1m, m != n}, = {0, 1}. Start by giving a prose proof idea (as in Sipser).

3a
S --> 1A0
A --> 0A | 1A | 0 | 1

3c
S --> A|B
A --> aA | bA |
B --> aB | cB |

3d
S --> aSa | bSb | cSc | AAB
A --> a | b | c
B --> aB | bB | cB |

1
S -> (0|1)*(00|11)(0|1)*

I hope this helps you. Acording to chegg protocol, I was able to answer only 4 sub-questions. For any help or assistance please comment.

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