Discussion
Language \(L_{1}\) is defined by the grammar: \(S_{1} \rightarrow aS_{1}b \mid \varepsilon\)
Language \(L_{2}\) is defined by the grammar: \(S_{2} \rightarrow abS_{2} \mid \varepsilon\)
Consider the following statements:
\(P\): \(L_{1}\) is regular
\(Q\): \(L_{2}\) is regular
Which one of the following is TRUE?
Answer: C
P is false and Q is true.
\(S_{1} \rightarrow aS_{1}b \mid \varepsilon\) generates \(L_{1} = \{a^{n}b^{n} : n \ge 0\}\). Recognising it needs to count the a’s to match the b’s, and the pumping lemma shows it is not regular, so P is false.
\(S_{2} \rightarrow abS_{2} \mid \varepsilon\) generates \(L_{2} = (ab)^{*}\), any number of repetitions of the string ab. It is a right-linear grammar, and the regular expression \((ab)^{*}\) describes it, so Q is true.
Options calling \(L_{1}\) regular, or \(L_{2}\) non-regular, are therefore wrong.
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