Unknown Properties of Context Free Languages Hindi | My Project HD | My Project HD
X

Properties of Context Free Languages Hindi

Computer Science Engineering Tutorials in Hindi | Theory of Computation

Properties of Context Free Languages Hindi

Computer Science Engineering Tutorials in Hindi | Theory of Computation



Unit 2

Types of Finite Automata

 

Topic  9 : Properties of Context Free Languages  Hindi 

 

Union  : यदि L1 और L2 दो context free languages है |तो उनके union L1 ∪ L2 भी Context Free होंगे

 

L1 = { anbncm | m >= 0 and n >= 0 } and L2 = { anbmcm | n >= 0 and m >= 0 }

L3 = L1 ∪ L2 = { anbncm ∪ anbmcm | n >= 0, m >= 0 } is also context free.

 

L1 कहता है कि a का number b के number के बराबर होनी चाहिए और L2 का कहना है कि b का Number c के number के बराबर होनी चाहिए। उनका union कहता है कि दो conditions में से कोई एक true है। तो यह Context Free languages  भी है।

 

Concatenation : 

यदि L1 और यदि L2 दो Context Free languages  हैं, तो उनका concatenation  L1.L2 भी Context Free होगा। उदाहरण के लिए

 

L1 = { anbn | n >= 0 } and L2 = { cmdm | m >= 0 }

L3 = L1.L2 = { anbncmdm | m >= 0 and n >= 0} is also context free.

 

L1 कहता है कि a का number b के number के बराबर होनी चाहिए और L2 का कहना है कि c number d के number के बराबर होनी चाहिए। उनका concatenation  कहता है कि पहले का number b  के number के बराबर होनी चाहिए, फिर C का number D के number के बराबर होनी चाहिए। तो, हम एक  PDA  बना सकते हैं जो पहले a के लिए push करेगा , और b के लिए POP और, d के लिए c के तत्कालीन POP के लिए  push    करेगा। तो यह pushdown automata द्वारा Accept  किया जा सकता है, इसलिए यह  context free है।


 

Kleene Closure : 

यदि L1 context free है, तो इसका Kleene closure L1 * भी context free होगा। उदाहरण के लिए,

L1 = { anbn | n >= 0 }

L1* = { anbn | n >= 0 }* is also context free.

 

Intersection and complementation :

यदि L1 और यदि L2 दो context free  language हैं, तो उनके intersection  L1 need L2 को context free होने की आवश्यकता नहीं है। उदाहरण के लिए, L1 = {abncm | n> = 0 और m> = 0} और L2 = (ambncn | n> = 0 और m> = = 0) L3 = L1 2 L2 = {abncn | n> = 0} context free होने की आवश्यकता नहीं है। L1 कहता है कि a की संख्या b की संख्या के बराबर होनी चाहिए और L2 का कहना है कि b की संख्या c की संख्या के बराबर होनी चाहिए। उनके intersection का कहना है कि दोनों conditions को true होने की जरूरत है, लेकिन push down automata केवल दो की तुलना कर सकता है। इसलिए इसे push down automata द्वारा स्वीकार नहीं किया जा सकता है, इसलिए यह context free नहीं है। इसी प्रकार, context free language  L1 का complementation  जो - * - L1 है, उसे context free करने की आवश्यकता नहीं है।

 

Deterministic Context-free Languages

Deterministic  CFL | CFL का Sub  set  है जिसे Deterministic PDA द्वारा मान्यता दी जा सकती है। Deterministic PDA  में किसी दिए गए state  और input symbol  से केवल एक Move होता होता   है, अर्थात, इसके पास विकल्प नहीं है। DCFL होने के लिए एक language  के लिए यह स्पष्ट होना चाहिए कि PUSh या POP कब है।



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