Context-Sensitive Grammars and Linear-Bounded Automata | Zendy

Prem Nath | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Context-Sensitive Grammars and Linear-Bounded Automata

Author(s) -

Prem Nath

Publication year - 2016

Publication title -

international journal of computer network and information security

Language(s) - English

Resource type - Journals

eISSN - 2074-9104

pISSN - 2074-9090

DOI - 10.5815/ijcnis.2016.01.08

Subject(s) - rule based machine translation , computer science , bounded function , normalization (sociology) , grammar , automaton , context (archaeology) , algorithm , mathematics , theoretical computer science , artificial intelligence , mathematical analysis , linguistics , paleontology , philosophy , sociology , anthropology , biology

Linear-bounded automata (LBA) accept context-sensitive languages (CSLs) and CSLs are generated by context-sensitive grammars (CSGs). So, for every CSG/CSL there is a LBA. A CSG is converted into normal form like Kuroda normal form (KNF) and then corresponding LBA is designed. There is no algorithm or theorem for designing a linear-bounded automaton (LBA) for a context-sensitive grammar without converting the grammar into some kind of normal form like Kuroda normal form (KNF). I have proposed an algorithm for this purpose which does not require any modification or normalization of a CSG.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research