112 views

### A push down automaton that recognize exponential strings

How can I describe a Push Down Automaton that recognize the language $P=\{a^{2^n} | n \geq 0 \}$? My approach I know that the language can be described by a Turing Machine, but how i can the stack ...
150 views

### Proving this language is not context free using the pumping lemma

I am trying to prove why the below language is not context free. Note: this should be carried out by applying the pumping lemma for context free languages. To prove something with the pumping lemma, ...
27 views

### Is this language a context-free language? [duplicate]

I'm currently trying to figure out whether this language is context-free using the pumping lemma. $\qquad L = \{ v_1 v_2 v_1 v_2 \mid v_1 \in \{a, b\}^*, v_2 \in \{a, c\}^* \}$ I'm having trouble ...
2k views

### PDA or CFG for language $L= \{a^ib^j | 2i \leq 2j \leq 3i, i>0\}$

Can someone help with this $L= \{a^ib^j | 2i \leq 2j \leq 3i, i>0\}$
4k views

### Is Python a context-free language?

From Wikipedia: Off-side_rule#Implementation, there is a statement: ...This requires that the lexer hold state, namely the current indentation level, and thus can detect changes in indentation ...
153 views

2k views

### Existence of non-context free but decidable languages

I've been reading the decidablity and undecidability chapters in Sipser's "Intro to Theory of Computation" however I could not find an explanation on the existence of a language that is both non-...
### Is the language $\{a^n b^n c^i | i \leq n\}$ context free?
I'm trying to apply the CFL pumping lemma. And, I've already tried words $a^pb^p$ and $a^pb^pc^p$. Not sure where to go from here.