Theory Of Computations

Step 1: Understanding the base productions.
The productions and generate strings of length , which are trivially palindromes and have odd length.
Step 2: Understanding recursive productions.
The productions and add the same symbol to both ends of the string, preserving the palindrome property.
Step 3: Analyzing string length.
Each recursive step increases the string length by . Since the base strings have odd length, all derived strings will also have odd length.
Step 4: Final conclusion.
Therefore, the grammar generates exactly all odd-length palindromes over the alphabet .

Step 1: Definition of NP-completeness.
A problem is NP-complete if it satisfies two conditions: it is in NP, and every problem in NP can be reduced to it in polynomial time.
Step 2: Role of known NP-complete problems.
3-SAT is a well-known NP-complete problem. Reducing 3-SAT to another problem proves that the target problem is at least as hard as 3-SAT.
Step 3: Interpreting the reduction direction.
To show is NP-complete, a known NP-complete problem must reduce to , not the other way around.
Step 4: Final conclusion.
Thus, showing that 3-SAT can be reduced to in polynomial time is sufficient to prove NP-completeness.

Step 1: Understanding decidability.
A problem is decidable if there exists an algorithm that always terminates with a correct yes or no answer for all inputs.
Step 2: Analyzing each option.
Deciding whether a string belongs to a CFG language is decidable using parsing algorithms like CYK.
Checking whether a CFG generates an empty language is decidable.
Checking whether a CFG generates a finite language is also decidable.
Step 3: Identifying the undecidable problem.
Determining whether a context-free grammar is ambiguous is a well-known undecidable problem in formal language theory. There is no algorithm that can solve this for all CFGs.
Step 4: Final conclusion.
Hence, the undecidable problem is deciding whether a given context-free grammar is ambiguous.