4
$\begingroup$

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 cs.

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

Improve this question
$\endgroup$
5
  • $\begingroup$ BTW, I previously posted this in the Math forum but got no response and I thought this might a more appropriate StackExchange: math.stackexchange.com/questions/4547415/… $\endgroup$
    – sligocki
    Commented Oct 11, 2022 at 15:11
  • 1
    $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Commented Oct 11, 2022 at 19:16
  • $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Commented Oct 11, 2022 at 19:22
  • $\begingroup$ 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. $\endgroup$
    – sligocki
    Commented Oct 12, 2022 at 2:13
  • 1
    $\begingroup$ Also check the definition of local languages (en.wikipedia.org/wiki/Local_language_(formal_language)) for a related restriction. $\endgroup$
    – Sylvain
    Commented Oct 12, 2022 at 15:55

1 Answer 1

Reset to default
4
$\begingroup$

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.

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 discuss this.

A few more links about ngram and backoff language models: An Empirical Study of Smoothing Techniques for Language Modeling, Unary Data Structures for Language Models, Faster and Smaller N-Gram Language Models.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – sligocki
    Commented Oct 12, 2022 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.