Question

Let $\sum _{}=\left\{0,1\right\}$. Let B be the collection of strings that contain at least one 1 in their second half. In other words,

a. Give a PDA that recognizes B

b. Give a CFG that generates B .

Short answer

a

b

$S\to XY$
$X\to AB$
$Y\to A1A\left|A1B\right|A1X\left|B1X\right|X1X$

$A\to 00*|\epsilon$
$B\to 11*|\epsilon$

Step-by-step solution

Explain Context-free Grammar and Pushdown Automata

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.

Give a PDA that recognizes B

a Consider the given,

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

defined as $(Q,\sum _{},\tau ,\delta ,q_{0,}F)$wherelocalid="1662190593189" $Q=\left\{q_0,q_1,q_2\right\},\sum _{}=\left\{0,1\right\},\tau =\left\{x\right\},F=\left\{q_2\right\}$

The PDA is as follows,

a

Give a CFG that generates B .

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.