Abstract
In this thesis, we will study very small full trios and full AFLs inside the family of context-free languages. Especially, we are interested in the existence of the smallest nontrivial full trios and full AFLs. This is an old research subject, and it has not been studied much since the 1970s. A conjecture by Autebert et al. states that there does not exist a nontrivial minimal full trio inside the family of context-free languages (2) (see also (1)). First, we will show that there does not exist a nontrivial minimal full trio or a nontrivial minimal full AFL with respect to the bounded context-free languages. This result solves another old conjecture stated by Autebert et al. (1). Then we will try to generalize our result to also concern unbounded context-free languages. We will make some progress, but the problem still remains open.
| Identifer | oai:union.ndltd.org:oulo.fi/oai:oulu.fi:isbn978-951-42-9274-3 |
| Date | 04 November 2009 |
| Creators | Salmi, T. (Tuukka) |
| Publisher | University of Oulu |
| Source Sets | University of Oulu |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/doctoralThesis, info:eu-repo/semantics/publishedVersion |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess, © University of Oulu, 2009 |
| Relation | info:eu-repo/semantics/altIdentifier/pissn/0355-3191, info:eu-repo/semantics/altIdentifier/eissn/1796-220X |
Page generated in 0.0027 seconds