The Gateway to Computer Science Excellence
0 votes

Let $\Sigma = \{0,1\}$ and let $B$ be the collection of strings that contain at least one  $1$ in their second half. In other words, $B = \{uv \mid u \in \Sigma^{\ast}, v \in \Sigma^{\ast}1\Sigma^{\ast}\: \text{and} \mid u \mid \geq \mid v \mid \}$.

  1. Give a PDA that recognizes $B$.
  2. Give a CFG that generates $B$.
in Theory of Computation by Veteran (60.7k points) | 18 views

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,833 questions
57,723 answers
107,779 users