We have grammar with nonterminals $ X_1,...X_n$ terminals $V_t$ and rewriting rules of form:
$X_i \rightarrow a \in V_t $
$X_i \rightarrow X_jX_k, \ i \ge j , \ i > k $
How can I show that language generated by this grammar is regular?
I don't think this is duplicate question, because:
- I don't have concrete language, but set of nonterminals and set of terminals
- I have to show, that for every possible combination of terminals and nonterminals I get only language which is regular
If I had been given particular language, I could prove it by giving DFA, showing that rules are only of linear type,etc....