scratch
§ DFA to CFG via Colimits?
created 2021-08-25
- Can convert a CFG to DFA by keeping an arbitrary limit on the depth of the stack, counting how many elements are in the stack, and going to a failure state when we exceed the depth.
- If we do so, can get a DFA for each natural number --- this is the max stack depth we keep track of.
- Can we now define a colimit of these DFAs? does this recover the CFG?
- If so, what is the correct category? And is the colimit completion of DFA correspond to DPDA/CFG?
❦