91Ó°ÊÓ

Context-free grammar generates context-free languages. The regular

languages are the subset of the context-free languages that are an identical

set of languages accepted by pushdown automata.

a Consider the given,

Construct the pushdown automata P to determine the language B . The P can be

defined as $(Q,\underset{}{∑},\mathrm{τ},\mathrm{δ},q_{0,}F)$wherelocalid="1662190593189" $Q=\left\{q_0,q_1,q_2\right\},\underset{}{∑}=\left\{0,1\right\},\mathrm{τ}=\left\{x\right\},F=\left\{q_2\right\}$

The PDA is as follows,

a

Consider the given,

The CFG for the language is as follows,

The String S has the production of XY concatenation. The string X can consist of

any number of 1’s and 0’s that are represented by A and B . The string Y may

consist of at least only one 1 or one 1.

Therefore, the Context -free Grammar for the language B has been obtained.