patternMinor
Decide if this language is context free
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.
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 -> 0S1
S -> 1S1
S -> 1X
X -> 0X
X -> 1X
X -> @
Explanation: You can produce any words from
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.