Skip to main content
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.6k
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.7k
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.6k
1 vote

Finding the Smallest Language Class containing a given language definition

The question is about closure properties of regular languages. In your question it is asked what is the family tho which the quotient $RQ(L_1, L_2) = \{ w \mid wv \in L_1 \text{ for some } v \in L_2\}$...
Hendrik Jan's user avatar
  • 30.7k

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