HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Decide if this language is context free

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thisfreelanguagedecidecontext

Problem

I got this question for homework:

Decide if this language is context free or not:

$\qquad \{x@1^m: x \in \left\{0,1\right\}^*, m \in \mathbb{N}, x_m = 1\}$.

Intuitively I think it's not context-free because a $PDA$ can't remember the places of all the $1$'s in $x$.

I tried using the pumping lemma but couldn't find the right example to show the language is not context-free.

I'd be grateful for any lead.

Solution

I think the context free grammar with these productions and starting symbol S produces your language (assuming words start at index 0):

S -> 0S1

S -> 1S1

S -> 1X

X -> 0X

X -> 1X

X -> @

Explanation: You can produce any words from {0,1} with index < mand add a 1to the right part of the word. When you reach index m, you switch to X and continue the word from {0,1}. You can end the word by producing an @.

Context

StackExchange Computer Science Q#34110, answer score: 2

Revisions (0)

No revisions yet.