Aspire's Library
A Place for Latest Exam wise Questions, Videos, Previous Year Papers,
Study Stuff for MCA Examinations - NIMCET
Study Stuff for MCA Examinations - NIMCET
Previous Year Question (PYQs)
Any string of terminals that can be generated by the following context-free grammar, where $S$ is start nonterminal symbol
$S\to XY$
$X\to 0X\mid 1X\mid 0$
$Y\to Y0\mid Y1\mid 0$
$S\to XY$
$X\to 0X\mid 1X\mid 0$
$Y\to Y0\mid Y1\mid 0$
Solution
From $X\to 0X\mid 1X\mid 0$, $X$ generates any binary string ending with $0$.So, $X=(0+1)^*0$.
From $Y\to Y0\mid Y1\mid 0$, $Y$ generates any binary string starting with $0$.
So, $Y=0(0+1)^*$.
Now,
$S\to XY$
So, every string generated by $S$ contains one $0$ from the end of $X$ and one $0$ from the start of $Y$.
Therefore, every generated string has at least two $0$'s.
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
Ask Your Question or Put Your Review.
