Master’s thesis describes theoretical basics, solution design, and implementation of constituency (phrasal) parser for Czech language, which is based on a part of speech association into phrases. Created program works with manually built and annotated Czech sample corpus to generate probabilistic context free grammar within runtime machine learning. Parser implementation, based on extended CKY algorithm, then for the input Czech sentence decides if the sentence can be generated by the created grammar and for the positive cases constructs the most probable derivation tree. This result is then compared with the expected parse to evaluate constituency parser success rate.

In this thesis, three methods are investigated to express context-free tree languages by regular tree grammars. The first method is a characterization. We show restrictions to context-free tree grammars such that, for each restricted context-free tree grammar, a regular tree grammar can be constructed that induces the same tree language. The other two methods are approximations. An arbitrary context-free tree language can be approximated by a regular tree grammar with a restricted pushdown storage. Furthermore, we approximate weighted context-free tree languages, induced by weighted linear nondeleting context-free tree grammars, by showing how to approximate optimal weights for weighted regular tree grammars.

This work deals with syntax analysis problems based on multi-generation. The basic idea is to create computer program, which transforms one input string to n -1 output strings. An Input of this program is some plain text file created by user, which contains n grammar rules. Just one grammar from the input file is marked as an input grammar and others n -1 grammars are output grammars. This program creates list of used input grammar rules for an input string and uses corresponding output grammar rules for the creation of n -1 output strings. The program is written in C++ and Bison

Master's thesis is dealing with translation based on coupled finite automaton model. Coupled finite automaton contains input and output automaton. The input automaton makes syntactic analysis with an input string. Used rules from the input automaton control the output automaton, which generates an output string. In thesis is described a way of determinisation of the input automaton without loss of information about rules used in original automaton. The determinizitaion is divided into two parts - for finite and infinite translation specified by transducers. Then is presented a new pair automaton with increased computing power. This increased computing power consists in replace of input or output or just a part of automaton by context free grammar.

This work suggests and solves the implementation of the transformation of context-free grammars and the conversions between context-free grammars and pushdown automata. It makes acquainted with the models used in modern theory of formal languages. In the work are indicated all algorithms necessary for transformations and mutual conversions between context-free grammars and pushdown automata. Proposed is an object representing the grammar and the automaton in the programme. Described is the assigning of definitions of grammar and of the automaton, the solution of drawing the automaton on the screen and the creation of graphical user interface of the application. The resulting programme is developed as Jawa applet which is available on public internet pages www.convertcfg.php5.cz.

No description available.

Sequence alignment is one of the most intensely studied problems in bioinformatics, and is an important step in a wide range of analyses. An issue that has gained much attention in recent years is the fact that downstream analyses are often highly sensitive to the specific choice of alignment. One way to address this is to jointly sample alignments along with other parameters of interest. In order to extend the range of applicability of this approach, the first chapter of this thesis introduces a probabilistic evolutionary model for protein structures on a phylogenetic tree; since protein structures typically diverge much more slowly than sequences, this allows for more reliable detection of remote homologies, improving the accuracy of the resulting alignments and trees, and reducing sensitivity of the results to the choice of dataset. In order to carry out inference under such a model, a number of new Markov chain Monte Carlo approaches are developed, allowing for more efficient convergence and mixing on the high-dimensional parameter space. The second part of the thesis presents a directed acyclic graph (DAG)-based approach for representing a collection of sampled alignments. This DAG representation allows the initial collection of samples to be used to generate a larger set of alignments under the same approximate distribution, enabling posterior alignment probabilities to be estimated reliably from a reasonable number of samples. If desired, summary alignments can then be generated as maximum-weight paths through the DAG, under various types of loss or scoring functions. The acyclic nature of the graph also permits various other types of algorithms to be easily adapted to operate on the entire set of alignments in the DAG. In the final part of this work, methodology is introduced for alignment-DAG-based sequence annotation using hidden Markov models, and RNA secondary structure prediction using stochastic context-free grammars. Results on test datasets indicate that the additional information contained within the DAG allows for improved predictions, resulting in substantial gains over simply analysing a set of alignments one by one.

Le problème de séparation pour une classe de langages S est le suivant : étant donnés deux langages L1 et L2, existe-t-il un langage appartenant à S qui contient L1, en étant disjoint de L2 ? Si les langages à séparer sont des langages réguliers, le problème de séparation pour la classe S est plus général que le problème de l'appartenance à cette classe, et nous fournit des informations plus détaillées sur la classe. Ce problème de séparation apparaît dans un contexte algébrique sous la forme des parties ponctuelles, et dans un contexte profini sous la forme d'un problème de séparation topologique. Pour quelques classes de langages spécifiques, ce problème a été étudié en utilisant des méthodes profondes de la théorie des semigroupes profinis.Dans cette thèse, on s'intéresse, dans un premier temps, à la décidabilité de ce problème pour plusieurs sous-classes des langages réguliers. Dans un second temps, on s'intéresse à obtenir un langage séparateur, s'il existe, ainsi qu'à la complexité de ces problèmes.Nous établissons une approche générique pour prouver que le problème de séparation est décidable pour une classe de langages donnée. En utilisant cette approche, nous obtenons la décidabilité du problème de séparation pour les langages testables par morceaux, les langages non-ambigus, les langages localement testables, et les langages localement testables à seuil. Ces classes correspondent à des fragments de la logique du premier ordre, et sont parmi lesclasses de langages réguliers les plus étudiées. De plus, cette approche donne une description d'un langage séparateur, pourvu qu'il existe. / The separation problem, for a class S of languages, is the following: given two input languages, does there exist a language in S that contains the first language and that is disjoint from the second langage ?For regular input languages, the separation problem for a class S subsumes the classical membership problem for this class, and provides more detailed information about the class. This separation problem first emerged in an algebraic context in the form of pointlike sets, and in a profinite context as a topological separation problem. These problems have been studied for specific classes of languages, using involved techniques from the theory of profinite semigroups.In this thesis, we are not only interested in showing the decidability of the separation problem for several subclasses of the regular languages, but also in constructing a separating language, if it exists, and in the complexity of these problems.We provide a generic approach, based on combinatorial arguments, to proving the decidability of this problem for a given class. Using this approach, we prove that the separation problem is decidable for the classes of piecewise testable languages, unambiguous languages, and locally (threshold) testable languages. These classes are defined by different fragments of first-order logic, and are among the most studied classes of regular languages. Furthermore, our approach yields a description of a separating language, in case it exists.

SANTOS, Andrea Feitosa. Movimento do verbo e categorias vazias em I e V em um fragmento de gramática computacional do português. 2009.96f.Dissertação (Mestrado em Linguistica) – Universidade Federal do Ceará, Departamento de Letras Vernaculas, Programa de Pós-Graduação em Linguística, Fortaleza-CE, 2009. / Submitted by nazareno mesquita (nazagon36@yahoo.com.br) on 2012-06-21T16:00:03Z No. of bitstreams: 1 2009_diss_AFSantos.pdf: 616159 bytes, checksum: 59bd79e8c618b1d231d8b7b98b8f767e (MD5) / Approved for entry into archive by Maria Josineide Góis(josineide@ufc.br) on 2012-06-22T16:39:36Z (GMT) No. of bitstreams: 1 2009_diss_AFSantos.pdf: 616159 bytes, checksum: 59bd79e8c618b1d231d8b7b98b8f767e (MD5) / Made available in DSpace on 2012-06-22T16:39:36Z (GMT). No. of bitstreams: 1 2009_diss_AFSantos.pdf: 616159 bytes, checksum: 59bd79e8c618b1d231d8b7b98b8f767e (MD5) Previous issue date: 2009 / This work has a theoretical and methodological framework that is divided into two complementary areas: the Language and Computational/Implementacional. For its computational stamp, the first scope of this work is directly linked to the processing of natural language (PNL). Thus, it implements an automatic syntactic analysis (parsing) of expressions of Portuguese in a computational program from the Python library of NLTK, whose tests are represented in tree configurations that show slash categories of finite sentences of Portuguese. Although the stamp computing, this research elaborates a grammar fragment, modeled to capture specific features of linguistic structure of Portuguese, based on the formal model of description linguistic known as Context Free Grammar (CFG) Based on Features, with the purpose of demonstrate how the library of NLTK programs supports the implementation of parsers for analyzing the feature structure. For its stamp of language, it analyzes, according to X-bar Theory and the Minimalist Program, sentences in European and Brazilian variants of Portuguese, obtained from surveys in electronic corpora available on the web. And this work describes and discusses the category IP (inflectional phrase) within the hierarchical structure of constituents, according to the hypothesis of syntactic operation of visible and invisible movement of elements of language, specifically the movement of the verb / Esse trabalho possui um recorte teórico-metodológico que se decompõe em dois domínios complementares: o Linguístico e o Computacional/Implementacional. Pelo seu cunho computacional, o escopo primeiro desse trabalho está diretamente ligado ao processamento de língua natural (PLN). Desse modo, implementa-se uma análise sintática automática (parsing) de expressões de língua portuguesa em programas da biblioteca em Python do NLTK, cujas análises são representadas em forma de configurações arbóreas que demonstram categorias vazias de sentenças finitas do português. Ainda pelo cunho computacional, esse trabalho elabora um fragmento de gramática, modelado para capturar traços específicos da estrutura linguística do português, com base no modelo formal de descrição linguística conhecido como Gramática Livre de Contexto (CFG) Baseada em Traços, com a finalidade de demonstrar como a biblioteca de programas do NLTK dá suporte à realização dos analisadores sintáticos na análise da estrutura de traços. Pelo seu cunho lingüístico, analisa-se, de acordo com a Teoria X-barra e o Programa Minimalista, frases nas variantes europeia e brasileira da língua portuguesa, obtidas de pesquisas em corpora eletrônicos disponíveis na web. E ainda nesse trabalho, descreve-se e discute-se a categoria IP (sintagma flexional) dentro da sua estrutura hierárquica de constituintes, de acordo com a hipótese da operação sintática de movimento visível e não visível dos elementos linguísticos, especificamente o movimento do verbo

CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / Esse trabalho possui um recorte teÃrico-metodolÃgico que se decompÃe em dois domÃnios complementares: o LinguÃstico e o Computacional/Implementacional. Pelo seu cunho computacional, o escopo primeiro desse trabalho està diretamente ligado ao processamento de lÃngua natural (PLN). Desse modo, implementa-se uma anÃlise sintÃtica automÃtica (parsing) de expressÃes de lÃngua portuguesa em programas da biblioteca em Python do NLTK, cujas anÃlises sÃo representadas em forma de configuraÃÃes arbÃreas que demonstram categorias vazias de sentenÃas finitas do portuguÃs. Ainda pelo cunho computacional, esse trabalho elabora um fragmento de gramÃtica, modelado para capturar traÃos especÃficos da estrutura linguÃstica do portuguÃs, com base no modelo formal de descriÃÃo linguÃstica conhecido como GramÃtica Livre de Contexto (CFG) Baseada em TraÃos, com a finalidade de demonstrar como a biblioteca de programas do NLTK dà suporte à realizaÃÃo dos analisadores sintÃticos na anÃlise da estrutura de traÃos. Pelo seu cunho lingÃÃstico, analisa-se, de acordo com a Teoria X-barra e o Programa Minimalista, frases nas variantes europeia e brasileira da lÃngua portuguesa, obtidas de pesquisas em corpora eletrÃnicos disponÃveis na web. E ainda nesse trabalho, descreve-se e discute-se a categoria IP (sintagma flexional) dentro da sua estrutura hierÃrquica de constituintes, de acordo com a hipÃtese da operaÃÃo sintÃtica de movimento visÃvel e nÃo visÃvel dos elementos linguÃsticos, especificamente o movimento do verbo / This work has a theoretical and methodological framework that is divided into two complementary areas: the Language and Computational/Implementacional. For its computational stamp, the first scope of this work is directly linked to the processing of natural language (PNL). Thus, it implements an automatic syntactic analysis (parsing) of expressions of Portuguese in a computational program from the Python library of NLTK, whose tests are represented in tree configurations that show slash categories of finite sentences of Portuguese. Although the stamp computing, this research elaborates a grammar fragment, modeled to capture specific features of linguistic structure of Portuguese, based on the formal model of description linguistic known as Context Free Grammar (CFG) Based on Features, with the purpose of demonstrate how the library of NLTK programs supports the implementation of parsers for analyzing the feature structure. For its stamp of language, it analyzes, according to X-bar Theory and the Minimalist Program, sentences in European and Brazilian variants of Portuguese, obtained from surveys in electronic corpora available on the web. And this work describes and discusses the category IP (inflectional phrase) within the hierarchical structure of constituents, according to the hypothesis of syntactic operation of visible and invisible movement of elements of language, specifically the movement of the verb