The Context Free Grammar and Machine Translation

My friends who worked with me might know all these fancy words like Machine Translation. But most of my friends who don't know can refer my previous post. Here I will talk about the Synchronous context free grammar, chart parsing and Machine Translation. It is extension of my previous post 'syntax in MT'. Well some of computer science friends may also know about context free grammar and chart parsing. Some of them might seen chart parsing in compiler design and context free grammar in Theory of Computation. Well context free grammar, can be looked as simple conversion rules.
The context free grammar for infix expression looks like
A->A+A|A-A|A*A|A/A|a|b|c


where A is non-terminal and a,b,c,+,-,*,/ are terminal symbols.
The parse tree of operations 'a-b+c' will looks for the context free grammar is shown below.

The process of getting parse tree from the set of operation('a-b+c') is known as parsing. There are many parsing techniques but they are divided into basically two types of approaches

1. TopDown Parsing:-
2. Bottom up Parsing:-

But how context free grammar is useful for machine translate. The above context free grammar is for infix operations. Suppose i want to convert infix string to post-fix string, using the context free grammar. Then post-fix grammar will look like
A->AA+|AA-|AA*|AA/|a|b|c
And we should combine both infix and post-fix grammar such that they can be use for translation of infix to postfix.
Then the grammar is known as synchronous context free grammar and looks like
A->A+A;AA+|A-A;AA-|A*A|AA*|A+A;AA+|A/A;AA/|a;a|b;b|c;c
where symbols before ; represents the infix operations and symbols after ; represents the post-fix.
So translation process is shown below.

In the translation, rules are used for reordering operation only and first A+A is converted to AA+ using rule A->A+A;AA+ and then second rule is applied A->A-A;AA- . But Machine Translation supports insertion, deletion also, which are done at the node level only.
We get target postfix string as ab-c+

syntax in SMT

Statistical Machine Translation is widely used in European and Chinese languages. The idea behind Statistical Machine Translation is pretty simple, how human can decode or translate unknown language?. If you give some large thousand parallel word aligned corpus or a huge dictionary to a person who is not familiar with the language. Then, how person will understand or learn the language. Similarly you can give parallel corpus to machine and machine will learn the word alignment and process it. The machine can learn and read the huge parallel corpus which for human takes years to understand. But, question arises who is best, human or machine, weather human learns only lexical mapping. I still remember, the last class of course of natural language processing, when head of my department, Prof Rajeev Sangal sir asked students for their last doubts. And one of my dear friend GVS Reddy asked, why we build these parse trees?, why machine needs parse trees?. Is this is usual way, how human learns the language, weather humans also design the parse trees in their mind. Well at that Prof. Rajeev Sangal sir, had given answer in favor of question. Right now I know, there is whole branch of cognitive parsing which deals with this area, and one of my friend Phani Gadde doing working in it.
The same thing is realized by machine translation researchers, and new branch of statistical machine translation emerges which is known as syntax based machine translation. As human also learns bilingual grammar with learning word mapping. Similarly Syntax based Machine Translation also uses bilingual synchronous grammar and word mapping. Most of syntax based machine translation uses synchronous context free grammar. There are different variations of syntax based machine translations 1)string to parse Tree 2)parse Tree to parse Tree 3) parse tree to string. Although, most of the syntax based machine translation system does reordering, insertion and deletion of words in parse tree. The benefit of syntax based machine translation is that it supports long distance reordering. As most of the statistical machine translation system penalties the long distance reordering, but in syntax based SMT reordering is done at node level of parse tree. So it supports long distance reordering.