4 votes
Accepted

A context-sensite grammar for the language of sequences of two different types of parentheses with possible intersections?

Basically, the idea is that $($ and $)$ can commute with $[$ and $]$, but $($ cannot commute with $)$ – and same for $[$ and $]$. An essentially noncontracting grammar would be: $S \to \varepsilon \...
Nathaniel's user avatar
  • 15.5k
3 votes

Is matching pairs sufficient?

I assume that the Turing machine $M$ is allowed to be nondeterministic. In that case we need three positions. Consider the possibility that $M$ on a certain configuration may move either left or right....
Hendrik Jan's user avatar
  • 30.6k
2 votes

What's really meant by context-free in the term context-free grammar?

What's meant by "Context Free"? Ultimately that the applicability of a phrase structure rule, for a grammar, should be independent of the surrounding context, where it is applied. The fact ...
NinjaDarth's user avatar
1 vote
Accepted

Context Free Grammar: How to infer FIRST()

Recall that if $X \to Y_1…Y_k$ is a rule of the grammar, then: $\Sigma\cap\text{FIRST}(Y_1)\subseteq \text{FIRST}(X)$ if, for some $2\leqslant j \leqslant k$, $\varepsilon \in \bigcap\limits_{i=1}^{j-...
Nathaniel's user avatar
  • 15.5k

Only top scored, non community-wiki answers of a minimum length are eligible