# “Choose next word” as an alternative to phrase-structure grammar

Notation: For the sake of this question, let $$\sigma_X(x)$$ denote the symbol immediately following $$x$$ in the sentence $$X$$. Let $$a\in A$$ indicate that the symbol $$a$$ occurs in the sentence $$A$$ if $$A$$ is a sentence and ordinary set membership, otherwise.

I was thinking about possible alternatives to phrase-structure grammar and I was inspired by text prediction software.

In principle, it should be possible to specify the grammar of a language using only a vocabulary $$V$$, a set $$I\subseteq V$$ of valid starting words (the set of symbols which may be used to begin a sentence), and a 'select next from' function $$S:V\to\mathcal{P}(V)$$; where, for each $$v\in V$$, $$S(v)$$ is the set of symbols in $$V$$ which may succeed $$v$$. That is, if $$X$$ is a valid sentence then $$\forall x\in X.\sigma_X(x)\in S(x)$$.

The one possible advantage this might have over phrase-structure grammar is that it allows for arbitrarily long sentences (it may also place fewer restrictions on the the structure of valid sentences) - but this might come at the cost of more complex production rules (in the form of the 'select next from' function).

Is this a valid means of specifying the grammar of a language, and if so, what would be the most expedient means of specifying $$S$$ (particularly when the predecessors of a symbol affect the possible successors)?

Edit: As pointed out by Q the Platypus, the grammar I am describing is similar, though not identical, to a Greibach normal form. The production rules of a grammar in Greibach normal form take the form of $$A\to aA_1A_2\ldots A_n$$, where $$a$$ is terminal and the sequence of $$A_i$$ are nonterminal.

The key difference between what I am attempting to describe and Greibach normal form is that there is no limit to length of a sentence. This might be put in Greibach normal form if the production rules could be specified by an expression like...

$$A\to a\bigsqcup_{i=1}^\beta A_i$$

...(using $$\sqcup$$ for concatenation) for every ordinal $$\beta$$.

The idea behind the 'select next' function was to provide a means of constructing arbitrarily long sentences and assessing whether an infinitely long sentence is valid (this could be done analogously to induction).

It also occurs to me that such sentences could, in principle, be without start or endpoint. Since each symbol depends only on the one(s) before it, you could have a 'select previous from' function that takes a symbol and determines which symbols might precede it and use that to create a sentence order-isomorphic to the integers.

Edit: It might be possible to express the aforementioned 'select next' and 'select previous' in terms of right and left recursion, respectively, with $$A\to aA$$ for right recursion and $$A\to Aa$$ for left recursion. In both cases, we must also have $$A\to\varepsilon$$, with $$\varepsilon$$ the empty string, as a production rule.

• This sounds like Greibach normal form – Q the Platypus May 16 at 2:01
• @QthePlatypus Thanks! I wasn't familiar with Greibach normal form. After reading up on it, I can say that I have almost the same idea, but with the caveat that the sequence of nonterminals succeeding the starting symbol need not be finite. This was the main reason for providing the set of next possible characters on a symbol-by-symbol basis, rather than relying on the sentence structure as a whole. – R. Burton May 16 at 13:47

I'm not sure if this is precisely what you're describing but, sentences can be generated via transitions such as: $$P(x_t|x_{t-1},\cdots,x_1)$$, where a sentence is comprised of words $$x_1x_2\cdots x_n$$. The probability function here simply counts the estimated frequency of the word $$x_t$$ given the past, and will be exactly 0 for disallowed word sequences (assuming your corpus of sentences has no grammatical errors). By the rules of probability this can be reduced to:
$$P(x_1\cdots x_n)=P(x_n|x_{n-1}\cdots x_1)P(x_{n-1}|x_{n-2}\cdots x_1)\cdots P(x_1).$$
By selecting $$x_t$$ with high probability, this effectively replicates current state-of-the-art techniques used for generating sentences in machine learning. This is generally referred to as Beam Search.