NIC-NIELIT STA 2020
October 4, 2023ICT
October 4, 2023Nielit Scientist-B 17-12-2017
| Question 11 |
P1: The language generated by some CFG contains any words of length less than some given number n.
P2: Let L1 be CFL and L2 be regular, to determine whether L1 and L2 have common elements
P3: Any given CFG is ambiguous or not
P4: For any given CFG G, to determine whether ɛ belongs to L(G)
| P2 only | |
| P1 and P2 only | |
| P2 and P3 only | |
| P3 only |
A problem is decidable if we can construct a Turing machine which will halt in finite amount of time for every input and give answer as ‘yes’ or ‘no’. A decidable problem has an algorithm to determine the answer for a given input.
Examples
Equivalence of two regular languages:Given two regular languages, there is an algorithm and Turing machine to decide whether two regular languages are equal or not.
Finiteness of regular language: Given a regular language, there is an algorithm and Turing machine to decide whether regular language is finite or not.
Emptiness of context free language: Given a context free language, there is an algorithm whether CFL is empty or not.
Undecidable Problems
A problem is undecidable if there is no Turing machine which will always halt in finite amount of time to give answer as ‘yes’ or ‘no’. An undecidable problem has no algorithm to determine the answer for a given input.
Examples
Ambiguity of context-free languages: Given a context-free language, there is no Turing machine which will always halt in finite amount of time and give answer whether language is ambiguous or not.
Equivalence of two context-free languages: Given two context-free languages, there is no Turing machine which will always halt in finite amount of time and give answer whether two context free languages are equal or not.
Everything or completeness of CFG: Given a CFG and input alphabet, whether CFG will generate all possible strings of input alphabet (∑*)is undecidable.
Regularity of CFL, CSL, REC and REC: Given a CFL, CSL, REC or REC, determining whether this language is regular is undecidable.
A problem is decidable if we can construct a Turing machine which will halt in finite amount of time for every input and give answer as ‘yes’ or ‘no’. A decidable problem has an algorithm to determine the answer for a given input.
Examples
Equivalence of two regular languages:Given two regular languages, there is an algorithm and Turing machine to decide whether two regular languages are equal or not.
Finiteness of regular language: Given a regular language, there is an algorithm and Turing machine to decide whether regular language is finite or not.
Emptiness of context free language: Given a context free language, there is an algorithm whether CFL is empty or not.
Undecidable Problems
A problem is undecidable if there is no Turing machine which will always halt in finite amount of time to give answer as ‘yes’ or ‘no’. An undecidable problem has no algorithm to determine the answer for a given input.
Examples
Ambiguity of context-free languages: Given a context-free language, there is no Turing machine which will always halt in finite amount of time and give answer whether language is ambiguous or not.
Equivalence of two context-free languages: Given two context-free languages, there is no Turing machine which will always halt in finite amount of time and give answer whether two context free languages are equal or not.
Everything or completeness of CFG: Given a CFG and input alphabet, whether CFG will generate all possible strings of input alphabet (∑*)is undecidable.
Regularity of CFL, CSL, REC and REC: Given a CFL, CSL, REC or REC, determining whether this language is regular is undecidable.