A PHP Error was encountered

Severity: Warning

Message: preg_match(): Compilation failed: unmatched closing parenthesis at offset 38

Filename: hooks/Check_user.php

Line Number: 222

Backtrace:

File: /home/b2z283hyjn3q/public_html/application/hooks/Check_user.php
Line: 222
Function: preg_match

File: /home/b2z283hyjn3q/public_html/application/hooks/Check_user.php
Line: 89
Function: getOS

File: /home/b2z283hyjn3q/public_html/application/hooks/Check_user.php
Line: 12
Function: anylisis

File: /home/b2z283hyjn3q/public_html/index.php
Line: 315
Function: require_once

Unknown Types of Grammar in TOC in Hindi | Chomsky Hierarchy in Theory of Computation | My Project HD | My Project HD
X

Types of Grammar in TOC in Hindi | Chomsky Hierarchy in Theory of Computation

Computer Science Engineering Tutorials in Hindi | Theory of Computation

Types of Grammar in TOC in Hindi | Chomsky Hierarchy in Theory of Computation

Computer Science Engineering Tutorials in Hindi | Theory of Computation



Unit 3

Grammars

 

Topic  1  : Types of Grammar in TOC in Hindi  | Chomsky Hierarchy in Theory of Computation

Chomsky Hierarchy  के अनुसार, Grammar के 4 type होते हैं –

  1. Type 0 (Recursively enumerable),
  2.  Type 1 (Context-sensitive),
  3.  Type 2 (Context-free),
  4.  Type 3. (Regular Grammar)

 

Grammar Type
Grammar Accepted
Language Accepted
Automaton
Type 0
Unrestricted grammar
Recursively enumerable language
Turing Machine
Type 1
Context-sensitive grammar
Context-sensitive language
Linear-bounded automaton
Type 2
Context-free grammar
Context-free language
Pushdown automaton
Type 3
Regular grammar
Regular language
Finite state automaton

 

Types of Grammar in TOC in Hindi  | Chomsky Hierarchy in Theory of Computation

 

निम्नलिखित illustration पर एक नज़र डालें। यह प्रत्येक प्रकार के Grammar के scope को दर्शाता है –

Type-0 grammars :

Type 0 Grammar में सभी recursively enumerable  शामिल हैं। वे सभी Language को उत्पन्न करते हैं जिन्हें Turing machine द्वारा recognized किया  है। इन Language को recursively enumerable या Turing-recognizable languages  के रूप में भी जाना जाता है। ध्यान दें कि यह recursive languages से अलग है, जिसे हमेशा रुकने वाली Turing machine द्वारा तय किया जा सकता है।

Example :

S → ACaB

Bc → acB

CB → DB

aD → Db

 

 

Type-1 grammars :

grammars context-sensitive languages generate करते हैं। productions के रूप में होना चाहिए

α A β → α γ β

α A β → α γ β

and α, β, γ (T N)* (Strings of terminals and non-terminals)

String α और β empty हो सकते हैं, लेकिन non-empty होना चाहिए।

 

Example :

AB → AbBc 
A → bcA 
B → b

 

 

Type - 2 Grammar :  

Type - 2 Grammar  context-free languages  generate करते हैं। productions A → γ के form मे होना चाहिये ।

where A N (Non terminal)

and γ (T N)* (String of terminals and non-terminals).

 

 

Example :

S → X a 
X → a 
X → aX 
X → abc 
X → ε

 

 

Type - 3 Grammar :

Type - 3 Grammar regular languages generate करते हैं। Type -3 Grammar में left-hand side एक single non-terminal होना चाहिए और एक single terminal या एक single terminal के बाद right-hand side  से एक ही terminal होना चाहिए।

productions  X → a or X → aY के form  मे होना चाहिये

where X, Y N (Non terminal)

and a T (Terminal)

 

Example :

X → ε 
X → a | aY

Y → b



More Tutorials

Web Technology Tutorials in Hindi

Web Technology Tutorials in Hindi

Read More
Diploma engineering tutorial for polytechnic collage

Diploma Engineering Tutorial

Read More
Final Year Projects for Computer Science with Source Code

Final Year Projects for Computer Science with Source Code

Read More