# Generating an "approximate" grammar

This is my first time posting here, so I hope I'm on topic. I have a table of natural-language data of the form

[Underlying] -> [Observed]
ABC -> abcd
EFGH -> eghf
IJK -> ik
LMNOP -> lnop
LNOP -> lnop


and so on. There are around 5000 more of these, but this is a sort of representative sample of things that go on. For the most part, it is fairly obvious which underlying states correspond to which observed state, but sometimes things get deleted, sometimes adjacent states swap spots, sometimes things get added, and sometimes two underlying sequences have the same observed sequence of characters. In the list of productions, assume that I have tagged each uppercase (underlying) state with its corresponding lowercase (observed) state. So in EFGH -> eghf, my program knows that f and g have switched spots in the output.

Now when the program is given a new string, it is completely untagged. So given eghf, it would have to somehow deduce that EFGH was the underlying sequence of states. I would like to be able to output all productions that could have occurred, given a string with a substring that is an observed string. For example, if my program is given the string xxxxlnopxx it should output xxxx[LMNOP]xx as well as xxxx[LNOP]xx. We know there is only one observed substring (so we don't have to worry about, say, abcd hiding in the xxxx part of the string). There is no distributional data at all on how often each production happens, so I would simply output every possible parse if more than one exists. Is this a special case of some kind of parsing algorithm? I guess the finiteness of the data means I could simply make a dictionary of all 5000 observed -> {set of underlying}, and then search for substrings, but one of the motivations of my exercise is to see "how" context-free/regular/context-sensitive my list of productions is. For example, perhaps the grammar reduces to something context-free, minus a couple of exceptions that can be hard-coded in. This is something I'd like to detect if possible.

Thanks in advance for the help! I would equally appreciate a link to a paper or outside resource that has solved a similar problem.

• – D.W.
Mar 8 at 22:42
• @D.W. I had not heard of this term. Thanks for the references! Mar 8 at 22:59