###### NIC-NIELIT STA 2020

October 4, 2023###### ICT

October 4, 2023# Nielit Scientist-B 17-12-2017

Question 11 |

**Which of the following are undecidable?**

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 |

__Decidable Problems__

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.

__Decidable Problems__

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.