# Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | future lectures)

On 01.12.2014 at 12:20 in S1, there is the following noon lecture:

# Old and new Transformations of Grammars: Structural, Algorithmic and Linguistic Applications

## Eli Shamir

## Abstract

Formal grammars provide a rich combinatorial theory and useful applications. We consider primarily the context–free [CF] model, its sub-models and "mild" extensions as well. The known transformations, simple and subtle, between various forms of the grammars encompass much of the theory and the applications: parsing schemes in compiler's technology, homomorphisms theorems, hardest context-free languages and more.

Our novel scheme utilizes heavily the manner CFG derives its trees and terminal strings, graded by the derivation semi-order on the symbols. Essentially, alternate pairs of spread and rotate operations, which will be defined, enable transition from product of factors to union of components.

They create an operation-tree which transforms the original grammar at the root into a bunch of elongated thin threads at the leaves of the tree-namely

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | future lectures)

Webmaster: kamweb.mff.cuni.cz Modified: 25. 02. 2019