2
$\begingroup$

I'm not sure about the relation between indexed languages (generated by indexed grammars--Aho) and scattered context languages (generated by scattered context grammars--J Hopcroft).

I think that scattered context languages properly include indexed languages but couldn't find any references.

Also, to make things more clear, I know that recently there is a new definition of scattered context grammars so they can generate all RE sets. But my question is based on the original definition by Hopcroft. So it is still open that whether CSLs properly includes scattered context languages.

Thanks a lot

$\endgroup$

0

Your Answer

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