<p>Yes, this is identical to a <em>bigram</em> model, a Markov model with order 2. Briefly, each state corresponds to a context of up to <code>n-1</code> symbols, and each arc represents the <code>n</code>'th symbol that transitions you to another state (again encoding a context of up to <code>n-1</code> symbols, so you lose some history).</p>
<p>Since your transition function is conditioned on the state (which only holds one token, in this example) your intuition about not being able to remember the <code>a</code> or <code>b</code> in <code>(ac*a|bc*b)</code> is correct, except that it would need to be <code>(ac+a|bc+b)</code> to ensure you enter the <code>c</code> state. For example, starting in a state with an empty context (sometimes called the <em>unigram state</em>), reading an <code>a</code> brings you to the <code>a</code> state, and reading a <code>c</code> brings you to the <code>c</code> state, but loses the information about where you came from.</p>
<p>You may be interested in this chapter on ngram language models (exactly what you described, but describing a probability distribution rather than set inclusion): <a href="https://web.stanford.edu/%7Ejurafsky/slp3/3.pdf" rel="nofollow noreferrer">Speech and Language Processing, Chapter 3.</a></p>
<p>One major issue with this type of model is that if you increase the context length (rather than remembering just one token, you remember several), the state complexity increases exponentially with the size of the vocabulary. There is a special type of ngram model called <em>backoff</em> ngram models designed specifically to address this issue. Sections 3.5.3 and 3.7 of <a href="https://web.stanford.edu/%7Ejurafsky/slp3/3.pdf" rel="nofollow noreferrer">1</a> discuss this.</p>
<p>A few more links about ngram and backoff language models: <a href="https://dash.harvard.edu/bitstream/handle/1/25104739/tr-10-98.pdf" rel="nofollow noreferrer">An Empirical Study of Smoothing Techniques for Language Modeling</a>, <a href="https://static.googleusercontent.com/media/research.google.com/ko//pubs/archive/37218.pdf" rel="nofollow noreferrer">Unary Data Structures for Language Models</a>, <a href="http://aclanthology.lst.uni-saarland.de/P11-1027.pdf" rel="nofollow noreferrer">Faster and Smaller N-Gram Language Models</a>.</p>

CC BY-SA 4.0
2022-10-12T16:58:04.040Z
Thank you for all the reading pointers @MRC! This is really helpful, I have seen n-gram before, but didn't think about it in this context. Actually, I had been thinking of calling this a "Markov" language b/c the words it describes are exactly the possible state sequences from a specific Markov Chain.
sligocki
CC BY-SA 4.0
2022-10-12T09:25:46.570Z
2022-10-13T02:17:10.907Z
2022-10-13T02:17:10.907Z
MRC
<p>I have a system that is deciding a subset of regular languages and am curious if anyone has seen this type before and if it has a name I could use to research more.</p>
<p>Specifically consider the collection of formal grammars with the following restrictions:</p>
<ul>
<li>There is a bijection between the terminal symbols and non-terminal symbols. In this post, I will use lowercase letters for terminal symbols and their uppercase counterparts as the associated non-terminal.</li>
<li>All production rules are of the form: <code>A -&gt; bB</code> or <code>A -&gt; ε</code>.</li>
</ul>
<p>So, these are basically regular grammars with the restriction that all rules which produce a terminal <code>b</code> must then have the associated non-terminal <code>B</code> directly afterwards. From the point of view of a finite automata, any automata that writes a <code>b</code> must enter the same state <code>B</code>.</p>
<p>I believe the collection of languages described by these grammars are a proper subset of regular languages. For example, I don't think it can describe the regular language <code>(ac*a|bc*b)</code> because it cannot &quot;remember&quot; whether the string started with <code>a</code> or <code>b</code> while processing through the <code>c</code>s.</p>
<p>Does anyone know if this type of language/grammar has been studied and how I could find more information about it if so? Thanks!</p>

CC BY-SA 4.0
2022-10-11T15:11:03.320Z
BTW, I previously posted this in the Math forum but got no response and I thought this might a more appropriate StackExchange: https://math.stackexchange.com/questions/4547415/does-this-formal-language-family-have-a-name
sligocki
CC BY-SA 4.0
2022-10-11T19:16:08.630Z
So, as far as I understand it, languages generated by such grammars are exactly those that can be expressed by forbidding certain two-letter combinations to appear in the string, or certain letters to appear at the start or at the end. This is a very restricted subclass of star-free regular languages.
Emil Jeřábek
CC BY-SA 4.0
2022-10-11T19:22:29.560Z
In particular, there are only finitely many such languages over any fixed alphabet, so I doubt that it was really studied as a class of its own.
Emil Jeřábek
CC BY-SA 4.0
2022-10-12T02:13:57.013Z
Thanks @EmilJeřábek. That characterization (excluding two-letter combinations) sounds right to me. The reference to star-free / counter-free languages was a helpful place to start reading.
sligocki
CC BY-SA 4.0
2022-10-12T15:55:22.317Z
Also check the definition of _local languages_ (https://en.wikipedia.org/wiki/Local_language_(formal_language)) for a related restriction.
Sylvain
<fl.formal-languages><regular-language><grammars>
Subset of regular languages
sligocki
# Subset of regular languages

(Asked by: username_0 on 2022-10-11)

I have a system that is deciding a subset of regular languages and am curious if anyone has seen this type before and if it has a name I could use to research more.

Specifically consider the collection of formal grammars with the following restrictions:

* There is a bijection between the terminal symbols and non-terminal symbols. In this post, I will use lowercase letters for terminal symbols and their uppercase counterparts as the associated non-terminal.
* All production rules are of the form: `A -> bB` or `A -> ε`.

So, these are basically regular grammars with the restriction that all rules which produce a terminal `b` must then have the associated non-terminal `B` directly afterwards. From the point of view of a finite automata, any automata that writes a `b` must enter the same state `B`.

I believe the collection of languages described by these grammars are a proper subset of regular languages. For example, I don't think it can describe the regular language `(ac*a|bc*b)` because it cannot "remember" whether the string started with `a` or `b` while processing through the `c`s.

Does anyone know if this type of language/grammar has been studied and how I could find more information about it if so? Thanks!

**Tags:** fl.formal-languages, regular-language, grammars
> **Comments:**
> **username_0**: BTW, I previously posted this in the Math forum but got no response and I thought this might a more appropriate StackExchange: https://math.stackexchange.com/questions/4547415/does-this-formal-language-family-have-a-name  
> **username_1**: So, as far as I understand it, languages generated by such grammars are exactly those that can be expressed by forbidding certain two-letter combinations to appear in the string, or certain letters to appear at the start or at the end. This is a very restricted subclass of star-free regular languages.  
> **username_1**: In particular, there are only finitely many such languages over any fixed alphabet, so I doubt that it was really studied as a class of its own.  
> **username_0**: Thanks @EmilJeřábek. That characterization (excluding two-letter combinations) sounds right to me. The reference to star-free / counter-free languages was a helpful place to start reading.  
> **username_2**: Also check the definition of _local languages_ (https://en.wikipedia.org/wiki/Local_language_(formal_language)) for a related restriction.  

---

## 1 answers

### Answer by username_3 on 2022-10-12. Score: 4 | Accepted answer

Yes, this is identical to a *bigram* model, a Markov model with order 2. Briefly, each state corresponds to a context of up to `n-1` symbols, and each arc represents the `n`'th symbol that transitions you to another state (again encoding a context of up to `n-1` symbols, so you lose some history).

Since your transition function is conditioned on the state (which only holds one token, in this example) your intuition about not being able to remember the `a` or `b` in `(ac*a|bc*b)` is correct, except that it would need to be `(ac+a|bc+b)` to ensure you enter the `c` state. For example, starting in a state with an empty context (sometimes called the *unigram state*), reading an `a` brings you to the `a` state, and reading a `c` brings you to the `c` state, but loses the information about where you came from.

You may be interested in this chapter on ngram language models (exactly what you described, but describing a probability distribution rather than set inclusion): [Speech and Language Processing, Chapter 3.](https://web.stanford.edu/%7Ejurafsky/slp3/3.pdf)

One major issue with this type of model is that if you increase the context length (rather than remembering just one token, you remember several), the state complexity increases exponentially with the size of the vocabulary. There is a special type of ngram model called *backoff* ngram models designed specifically to address this issue. Sections 3.5.3 and 3.7 of [1](https://web.stanford.edu/%7Ejurafsky/slp3/3.pdf) discuss this.

A few more links about ngram and backoff language models: [An Empirical Study of Smoothing Techniques for Language Modeling](https://dash.harvard.edu/bitstream/handle/1/25104739/tr-10-98.pdf), [Unary Data Structures for Language Models](https://static.googleusercontent.com/media/research.google.com/ko//pubs/archive/37218.pdf), [Faster and Smaller N-Gram Language Models](http://aclanthology.lst.uni-saarland.de/P11-1027.pdf).

> **Comments:**
> **username_0**: Thank you for all the reading pointers @MRC! This is really helpful, I have seen n-gram before, but didn't think about it in this context. Actually, I had been thinking of calling this a "Markov" language b/c the words it describes are exactly the possible state sequences from a specific Markov Chain.  

---

