[Solved]: Automata Theory Questions: Rule Trees, Context-Free Grammar, Proving Ambiguity

(1) It’s always helpful to start listing some strings to get an idea of what kind of language we accept. I’m going to be making some assumptions here, but you should verify that these assumptions are true with whoever gave the assignment (they might be bad assumptions). $delta$ is the start symbol. We want to derive this until we get a string of only terminal symbols, either $0$s or $1$s. What’s the smallest string we can derive? Well, we can get $0A$ from $delta$, and from $alpha A$ (I assume $alpha$ is any string), we can derive $alpha^T alpha alpha^T$; therefore, from $0A$ we can derive $0^T 0 0^T$. Since $T$ isn’t defined, I assume it’s a free variable – from context, I assume an integer – which means it can assume any natural value. Therefore, we can derive $0$, $00$, … (i.e., $0^+ = 00^*$) from $0A$. The next observation is that there is no way to get $epsilon$, the empty string. Only the $A$ symbol can ever be removed, and the only productions that add $A$ also add $0$. The final observation is that productions only add the $0$ terminal symbol, so whatever language the grammar generates, it’s a subset of $0^*$. In summary, we know that: 1. The language contains $0^+ = 0^1 + 0^2 + …$; 2. The language doesn’t contain $epsilon = 0^0$; 3. The language is a subset of $0^* = 0^0 + 0^1 + 0^2 + …$. I’m not entirely sure what a rule tree would look like for a context-sensitive grammar, so someone else might need to address that. To get the string $000$ one could apply the rules $delta rightarrow 0A rightarrow 0^T 0 0^T = 000$ by taking $T = 1$. (2) Something like this should work:

Start := 0 Inner 1 | 0 Start 1 Inner := 10 | 1 Inner 0 

Nonterminals are Start and Inner. Terminals are 0 and 1. Let’s consider how this works: first, Start can generate $0^{n-1} S 1^{n-1}$ by applying the rule Start := 0 Start 1 $n-1$ times. It can then get $0^n I 1^n$ by applying Start := 0 Inner 1. Next, we can get $0^n1^{k-1}0^{k-1}1^n$ by applying Inner := 1 Inner 0 $k – 1$ times. Finally, we apply Inner := 10 once to get $0^n1^k0^k1^n$. (3) See the approach given for problem (1). You should find the language looks roughly like $01, 11, 101, 1001, …, 10^n1, … = 01 + 10^*1$.