<p>Given </p>

<ul>
<li>an <a href="https://en.wikipedia.org/wiki/Long_short-term_memory" rel="nofollow noreferrer">LSTM</a> <span class="math-container">$N$</span> of a given size <span class="math-container">$A$</span>, </li>
<li>a sentence <span class="math-container">$S$</span> with a given number of words <span class="math-container">$B$</span>,</li>
<li>a <a href="https://en.wikipedia.org/wiki/Chomsky_hierarchy" rel="nofollow noreferrer">Chomsky grammar hierarchy level</a> <span class="math-container">$C$</span> in 0-3,</li>
<li>a Chomsky grammar <span class="math-container">$G$</span> of level <span class="math-container">$C$</span> of size <span class="math-container">$D$</span>,</li>
</ul>

<p>A given fixed, concrete grammar <span class="math-container">$G$</span> defines a set of sentences <span class="math-container">$S$</span> which have the structure described by the grammar.  The size parameter <span class="math-container">$D$</span> gives a bound on the complexity of <span class="math-container">$G$</span>.  Let's use the definition of an <a href="https://en.wikipedia.org/wiki/Unrestricted_grammar" rel="nofollow noreferrer">unrestricted grammar</a> <span class="math-container">$G = (V, \Sigma, P, S)$</span>, where </p>

<ul>
<li><span class="math-container">$V$</span> is a set of nonterminal symbols</li>
<li><span class="math-container">$\Sigma$</span> is a set of terminal symbols</li>
<li><span class="math-container">$P$</span> is a set of production rules and</li>
<li><span class="math-container">$S$</span> is a set of start symbols in <span class="math-container">$V$</span></li>
</ul>

<p>For our size measure <span class="math-container">$D$</span> we can adopt a simple rule such as <span class="math-container">$D=|V|+|\Sigma|+|P|$</span> where <span class="math-container">$|Q|$</span> is the number of elements in set <span class="math-container">$Q$</span>.</p>

<p>Assume that the input to <span class="math-container">$N$</span> is a vector of size <span class="math-container">$B$</span> of integers representing words of <span class="math-container">$S$</span>, and the output of <span class="math-container">$N$</span> is a single binary category with value 1 for <span class="math-container">$S$</span> in <span class="math-container">$G$</span> and 0 otherwise, and that the node weights of <span class="math-container">$N$</span> have been adjusted to optimally perform the recognition task.  In practice this would be through a labelled training process.  Let's assume that we have an oracle that gives us an optimal assignment of node weights.  The neural network architecture together with its size parameters (number of layers, number of nodes per layer and so on), together with the constant weights assigned to the nodes, comprise together a particular kind of computer program which operates in a fixed and well understood way.  In particular it is a kind of dataflow computation graph with some constant inputs, some variable inputs, some outputs and some feedback of certain node outputs as node inputs.   Once it has been configured, it operates in a deterministic and completely defined way.</p>

<p>Q1. Can <span class="math-container">$N$</span> recognize sentences (accept or reject) <span class="math-container">$S$</span>?</p>

<p>Q2. Is this a problem in Theoretical Computer Science?</p>

<p>Q3. If the <a href="https://cstheory.stackexchange.com/questions/2252/is-the-chomsky-hierarchy-outdated">Chomsky Hierarchy is too old-fashioned</a>, can you work this problem for the <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo" rel="nofollow noreferrer">Complexity Zoo</a>?</p>

CC BY-SA 4.0
2019-07-23T14:40:04.597Z
What is the role of $G$ and $D$ in the questions?
M.Monet
CC BY-SA 4.0
2019-07-23T16:21:27.267Z
I've added some details to the problem spec to clarify.
Lars Ericson
CC BY-SA 4.0
2019-07-23T16:26:57.147Z
The particular size definition could be varied to suit the responder.  I'm making this problem up as I go along; it's not from a book.
Lars Ericson
<machine-learning><context-free><complexity>
Sentences in what kinds of grammar in the Chomsky hierarchy can be parsed by an LSTM of a given size?
Lars Ericson
# Sentences in what kinds of grammar in the Chomsky hierarchy can be parsed by an LSTM of a given size?

(Asked by: username_0 on 2019-07-22)

Given

* an [LSTM](https://en.wikipedia.org/wiki/Long_short-term_memory) $N$ of a given size $A$,
* a sentence $S$ with a given number of words $B$,
* a [Chomsky grammar hierarchy level](https://en.wikipedia.org/wiki/Chomsky_hierarchy) $C$ in 0-3,
* a Chomsky grammar $G$ of level $C$ of size $D$,

A given fixed, concrete grammar $G$ defines a set of sentences $S$ which have the structure described by the grammar. The size parameter $D$ gives a bound on the complexity of $G$. Let's use the definition of an [unrestricted grammar](https://en.wikipedia.org/wiki/Unrestricted_grammar) $G = (V, \Sigma, P, S)$, where

* $V$ is a set of nonterminal symbols
* $\Sigma$ is a set of terminal symbols
* $P$ is a set of production rules and
* $S$ is a set of start symbols in $V$

For our size measure $D$ we can adopt a simple rule such as $D=|V|+|\Sigma|+|P|$ where $|Q|$ is the number of elements in set $Q$.

Assume that the input to $N$ is a vector of size $B$ of integers representing words of $S$, and the output of $N$ is a single binary category with value 1 for $S$ in $G$ and 0 otherwise, and that the node weights of $N$ have been adjusted to optimally perform the recognition task. In practice this would be through a labelled training process. Let's assume that we have an oracle that gives us an optimal assignment of node weights. The neural network architecture together with its size parameters (number of layers, number of nodes per layer and so on), together with the constant weights assigned to the nodes, comprise together a particular kind of computer program which operates in a fixed and well understood way. In particular it is a kind of dataflow computation graph with some constant inputs, some variable inputs, some outputs and some feedback of certain node outputs as node inputs. Once it has been configured, it operates in a deterministic and completely defined way.

Q1. Can $N$ recognize sentences (accept or reject) $S$?

Q2. Is this a problem in Theoretical Computer Science?

Q3. If the [Chomsky Hierarchy is too old-fashioned](https://cstheory.stackexchange.com/questions/2252/is-the-chomsky-hierarchy-outdated), can you work this problem for the [Complexity Zoo](https://complexityzoo.uwaterloo.ca/Complexity_Zoo)?

**Tags:** machine-learning, context-free, complexity
> **Comments:**
> **username_1**: What is the role of $G$ and $D$ in the questions?  
> **username_0**: I've added some details to the problem spec to clarify.  
> **username_0**: The particular size definition could be varied to suit the responder.  I'm making this problem up as I go along; it's not from a book.  

---

## 0 answers

