Question:
In the Chomsky hierarchy of formal languages, which type of grammar generates Context-Free Languages (CFL) accepted by Pushdown Automata?
औपचारिक भाषाओं की चॉम्स्की पदानुक्रम में, किस प्रकार का व्याकरण संदर्भ-मुक्त भाषाओं (CFL) को उत्पन्न करता है जिन्हें पुशडाउन ऑटोमेटा द्वारा स्वीकार किया जाता है?
Options:
- Type-2 Grammar
- Type-0 Grammar
- Type-1 Grammar
- Type-3 Grammar
- Type-2 Grammar (प्रकार-2 व्याकरण)
- Type-0 Grammar
- Type-1 Grammar
- Type-3 Grammar
Correct Answer: a)
Explanation:
Chomsky Hierarchy:
– Type-0: Unrestricted (Turing Machine)
– Type-1: Context-Sensitive (Linear Bounded Automata)
– Type-2: Context-Free (Pushdown Automata)
– Type-3: Regular (Finite Automata).
Therefore, Context-Free Languages correspond to Type-2.
– Type-0: Unrestricted (Turing Machine)
– Type-1: Context-Sensitive (Linear Bounded Automata)
– Type-2: Context-Free (Pushdown Automata)
– Type-3: Regular (Finite Automata).
Therefore, Context-Free Languages correspond to Type-2.
चॉम्स्की पदानुक्रम:
Type-3: नियमित भाषाएं (DFA/NFA)
Type-2: संदर्भ-मुक्त भाषाएं (Pushdown Automata)
Type-1: संदर्भ-संवेदनशील भाषाएं (LBA)
Type-0: अप्रतिबंधित भाषाएं (Turing Machine)।
Type-3: नियमित भाषाएं (DFA/NFA)
Type-2: संदर्भ-मुक्त भाषाएं (Pushdown Automata)
Type-1: संदर्भ-संवेदनशील भाषाएं (LBA)
Type-0: अप्रतिबंधित भाषाएं (Turing Machine)।