Discussion
Which of the following definitions generates the same Language as L, where \(L = \{WW^{R} \mid W \in \{a, b\}^{*}\}\)
Answer: B
The language \(L = \{ww^R\}\) is the set of even length palindromes over {a, b}, so each string is built by putting the same letter at both ends and repeating, until the empty string. The grammar \(S \to aSa \mid bSb \mid \epsilon\) does exactly this. The grammar with asb and bsa generates strings in which the ends differ, such as ab, which is not of the form ww^R, and the last option, which has no \(\epsilon\) rule, cannot generate the empty string, which is in L (with w empty). The keyed answer is the second option.
No comment is present. Be the first to comment.
Loading…
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development