Linked Questions

0
votes
0answers
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 ...
0
votes
1answer
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, ...
0
votes
0answers
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 ...
0
votes
1answer
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\}$
8
votes
2answers
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 ...
0
votes
1answer
153 views

Closure of context-free languages under “removal of a regular language from the right”

I have a homework that I can't solve can somebody help me? If $\Sigma$ is an alphabet, $R$ is regular and $L$ is context-free. Is the language $$P = \{\alpha\in\Sigma^*\mid \alpha\beta\in L\text{ for ...
1
vote
1answer
67 views

Is regular expression syntax regular?

Regular expressions are equivalent to DFA's and describe regular languages, but is the language used to construct regular expressions regular? My guess is that the original syntax (concat, | and *) ...
0
votes
1answer
566 views

Prove that $L = \{ a^ib^jc^k | i < j \ and \ i+2j +3 < k \}$ is not CFG

Can someone help me prove that $L = \{ a^ib^jc^k | i < j \ and \ i+2j+3 < k \}$ is not a context free language? I've tried applying the pumping lemma for CFGs and proving case by case (taking ...
0
votes
0answers
28 views

Generate a Grammar from a language(Non-CFL) [duplicate]

I tried to solve this question, We have this Language, L(g)={AA|A={0+1}*} The output(Productions) must be similar as these = {(11 11), (0 0), (1101 1101), etc..} The left side equal to right side.. ...
0
votes
1answer
347 views

Proving $L = \{0^i1^j0^i1^j\ |\ i+j > 0\}$ is not a context-free language [duplicate]

I have the language $L = \{0^i1^j0^i1^j\ |\ i+j > 0\}$ I and want to prove that it is not context-free by using the Pumping lemma for context-free languages. I am new to this field and I am having ...
-1
votes
1answer
59 views

using pumping lemma prove this language is not a context-free-language [duplicate]

How can one prove that the language below is not context-free using the pumping lemma? $$\{ a^i b^m a^j b^m a^k b^m \mid i,j,k,m \geq 0 \}$$
0
votes
2answers
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-...
2
votes
1answer
600 views

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.
0
votes
1answer
332 views

Is the language $L=\{a^nb^m \mid n>2^m\}$ context-free?

I cannot go on with this exercise: Determine whether $L = \{a^nb^m \mid n > 2^m \}$ is context-free. Let's suppose that $L$ is context-free. According to the pumping lemma, there exists $N > ...
0
votes
0answers
129 views

Why does $L=\{w\#s : |w|=|s|\, w,s\in \{0,1\}^{*}, w \neq s \} \notin CFL$ [duplicate]

Im trying to prove that $L=\{w\#s : |w|=|s|, w \neq s\} \notin CFL$ using the pumping lemma. So I said, let say $L \in CFL$ so by the pumping exists $p$ which is the pumping length of language $L$, I ...

15 30 50 per page
1 2
3
4 5
8