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

Problem Detail: 

I'm currently taking a class in Automata Theory and it's kicking my butt. I have an assignment that my teacher gave me that consists of three questions. I have no idea where to start. My teacher and I have a language barrier that I can't seem to break. If anyone could help me understand how to solve the following problems or guide me in the right direction, I would appreciate it! Sorry if I write some of the symbols wrong. I will attach images of the handout as well an assignment/answer sheet he gave us on a previous assignment. Thank you!!

1. Define the language generated by the grammar $G_c= (V_n, V_t, P, \delta)$ where:

   • $V_n = \{\delta, A\}$,
   • $V_t = \{0, 1\}$,
   • $P = \{(\delta, A0), (\delta, 0\delta 0), (\alpha A,\alpha^T \alpha \alpha^T)\}$

   Give a rule tree for one sentence of the language $L(G_c)$ generated by the grammar $G_c$.

2. Assume that we are given the language: $L(G_b) = \{0^n 1^k 0^k 1^n \mid k, n = 1, 2,... \}$. Find a context-free grammar for this language.

3. Assume we are given the following grammar $G_a = (V_n, V_t, P, \delta)$ where:

   • $V_n = \{\delta, A, B\}$,
   • $V_t = \{0, 1\}$, and
   • $P = \{(\delta, 0A), (\delta, 1B), (A, 1), (B, 0B), (B,1)\}$.

   Find the language $L(G_a)$ generated by the grammar $G_a$.

The Assignment: http://i.imgur.com/qx2hB1u.jpg

Previous Assignment + Answers:https://imgur.com/a/jO124

Asked By : Christy

Answered By : Patrick87

(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$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/24494

 Ask a Question

 Download Related Notes/Documents