PCP-Example

 





Comments

Post a Comment

Popular posts from this blog

Chomsky Hierarchy of languages

Image
 Chomsky classified the grammars into four types. They are Type-0, Type-1, Type-2 and Type-3. This is shown in the following diagram The description of these grammars are given in the following section 1. Type-0 Grammar Type-0 grammars represents exactly the languages recognized by the Turing Machine. This is also called as unrestricted or phrase-structured grammar. The general structure of this grammar is given below, where both the left and right hand side of the production may contain any number of terminals and variables. Example 1.1:  S -> ACaB                               Bc -> acB                               CB -> DB                                aD -> Db 2. Type-1 Grammar Type-1 grammars ...
Read more