New answers tagged

0 votes

Two-State Turing Machine for Parenthesis Matching

// Parenthesis matcher Turing Machine // test tapes states q0 q1 // list of state names, first is starting state symbols - ( ) [ { < > 0 1 tape test1 ( result1 test1 0 tape test2 ) result1 ...
Bill Wang'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
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
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
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
0 votes

Finding the Smallest Language Class containing a given language definition

The regular languages are indeed closed under the Right Quotient (RQ) operation. That is $RQ(L_1,L_2)$ also written as $L_1/ L_2$ is regular when both $L_1$ and $L_2$ are regular. The proof here (see ...
codeR's user avatar
  • 634
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.6k

Top 50 recent answers are included