| dc.contributor.advisor | Shankar, Priti | |
| dc.contributor.author | Adiga, B Suryanarayana | |
| dc.date.accessioned | 2026-01-21T10:01:06Z | |
| dc.date.available | 2026-01-21T10:01:06Z | |
| dc.date.submitted | 1987 | |
| dc.identifier.uri | https://etd.iisc.ac.in/handle/2005/8314 | |
| dc.description.abstract | A finite graph model for a context?free language is proposed.
The model is called an extended transition system; its nodes encode
[pushdown automata state, top stack symbol] pairs and its arcs encode
pushdown automaton transitions. Three applications of this model are
presented. Graph theoretic proofs of the Pumping Lemma, Parikh's
theorem and the Chomsky–Schützenberger theorem are given. A new regularity
test for deterministic context?free languages is given which has
complexity O(qt)4O(q t)^4O(qt)4 where qqq is the number of states and ttt the number
of stack symbols of the deterministic pushdown automaton for the
language. A new algorithm for the near minimal cost correction of
substitution errors in deterministic context?free languages is presented.
This algorithm has time complexity O(n)O(n)O(n) for a subclass of the deterministic
context?free language. | |
| dc.language.iso | en_US | |
| dc.relation.ispartofseries | T02558 | |
| dc.rights | I grant Indian Institute of Science the right to archive and to make available my thesis or dissertation in whole or in part in all forms of media, now hereafter known. I retain all proprietary rights, such as patent rights. I also retain the right to use in future works (such as articles or books) all or part of this thesis or dissertation | |
| dc.subject | Context?free language | |
| dc.subject | Extended transition system | |
| dc.subject | Deterministic pushdown automaton | |
| dc.title | Application of finite graph models of context fue languages. | |
| dc.type | Thesis | |
| dc.degree.name | PhD | |
| dc.degree.level | Doctoral | |
| dc.degree.grantor | Indian Institute of Science | |
| dc.degree.discipline | Engineering | |
