Properties of Context Free Languages Hindi

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 कब है।