Lang1 = {x|x does not contain the string ‘pg’} Lang2 = {x|x contains the…

To determine the difference in the minimum number of states required for Lang1 and Lang2, we analyze the minimal deterministic finite automata (DFA) for each language.
Lang1: Strings that do not contain the substring 'pg'.
We need a DFA that rejects any string containing 'pg'.
The minimal DFA has 3 states: one start state (no 'p' seen or 'p' seen) , 2nd for 'p' seen and one final state (after 'pg' is seen).
The start state transitions to itself on 'g' and to a new state on 'p'. The new state transitions to the trap state on 'g' and to itself on 'p'.
The trap state is non-accepting and transitions to itself on both inputs.
Lang2: Strings that contain the substring 'pg'.
We need a DFA that accepts strings containing 'pg' at least once.
The minimal DFA has 3 states: start (no 'p' seen), after 'p' (seen 'p' but not 'pg'), and after 'pg' (accepting).
From start, on 'p' go to after 'p'; on 'g' stay in start. From after 'p', on 'g' go to after 'pg'; on 'p' stay in after 'p'. After 'pg', stay in accepting state.
Minimum states for Lang1: 2. Minimum states for Lang2: 3. Difference: 3 - 3 = 0.
हिन्दी उत्तर:
Lang1: वे शब्द जिनमें 'pg' उपस्ट्रिंग नहीं होती।
हमें एक डीएफए चाहिए जो 'pg' वाले किसी भी शब्द को अस्वीकार करे।
न्यूनतम डीएफए में 2 राज्य होते हैं: एक शुरुआती राज्य (कोई 'p' नहीं देखा या 'p' देखा लेकिन 'g' नहीं) और एक ट्रैप राज्य ('pg' देखने के बाद)।
शुरुआती राज्य 'g' पर खुद पर जाता है और 'p' पर एक नए राज्य में जाता है। नए राज्य 'g' पर ट्रैप राज्य में जाता है और 'p' पर खुद पर जाता है।
ट्रैप राज्य गैर-स्वीकृत है और दोनों इनपुट पर खुद पर जाता है।
Lang2: वे शब्द जिनमें 'pg' उपस्ट्रिंग होती है।
हमें एक डीएफए चाहिए जो 'pg' कम से कम एक बार दिखने पर शब्द को स्वीकार करे।
न्यूनतम डीएफए में 3 राज्य होते हैं: शुरुआत (कोई 'p' नहीं देखा), 'p' के बाद ( 'p' देखा लेकिन 'pg' नहीं), और 'pg' के बाद (स्वीकृत)।
शुरुआत से, 'p' पर 'p' के बाद में जाएं; 'g' पर शुरुआत में रहें। 'p' के बाद से, 'g' पर 'pg' में जाएं; 'p' पर 'p' के बाद में रहें। 'pg' के बाद, स्वीकृत राज्य में रहें।
Lang1 के लिए न्यूनतम राज्य: 2। Lang2 के लिए न्यूनतम राज्य: 3। अंतर: 3 - 2 = 1।