Question

Automata and Computability Problems

Please check my work. Make necessary edits/corrections to my work. Please add more detail to number 2 for better understanding :)

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. 2. Answer each part for the following context-free grammar. I. II. III. IV. V. R> XRXS S -ать | bТа T → XTX | X | 8 х ► ab What are the variables and terminals of G? Which is the start symbol? Give three examples of strings in L(G). Give three examples of strings not in L(G). True or False: T = aba. True or False: T *** aba.

Answer 1

Answer:

1) The language that contains non-empty strings starting and ending with same symbol must also include single letter strings a and b.Therefore language is

L = {a, b, aa , bb, aba, bab, .....}

The grammar is :

S -> aAa | bAb | a | b

A -> aA | bA | ε

2)

I) Your answer is correct,

In the grammar usually variables are represented with capital letters and terminals represented with small letters and the start symbol is left side variable in first production of grammar.

  II & III answers of you are correct.

  IV )  False , because T could generate aba , but T is not a start symbol , so it alone could not generate any string.

  V ) True, because as explaned in IV when T produce aba before it any substring could definately present.