Linked Questions

0
votes
0answers
12 views

Regular Expression for a^nb^m such that n<= m+3 [duplicate]

I want to know if its possible to write a regular expression for a context free language: For example I have a language : L={a^n b ^m: n<= m +3} I have written the following regular expression ...
4
votes
2answers
2k 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 ...
77
votes
10answers
110k views

How to prove that a language is not regular?

We learned about the class of regular languages $\mathrm{REG}$. It is characterised by any one concept among regular expressions, finite automata and left-linear grammars, so it is easy to show that a ...
1
vote
1answer
39 views

Acceptance problem for CFGs is not regular

Let $ACFG$ be the language of all encodings $(C,x)$ where $C$ is a context free grammar that generates a language containing $x$, i.e. $ACFG$ is the acceptance problem for context free grammars. It ...
18
votes
3answers
1k views

Algorithm to test whether a language is context-free

Is there an algorithm/systematic procedure to test whether a language is context-free? In other words, given a language specified in algebraic form (think of something like $L=\{a^n b^n a^n : n \in \...
0
votes
1answer
67 views

$L = \{ a^{j!} \mid j \geq1\}$ is not context free by pumping lemma

How I use the pumping lemma to prove that the language $L = \{ a^{j!} \mid j \geq1\}$ is not context-free?
-1
votes
1answer
24 views

Is there any tiny tips to find counter example string for proving some language is not a CFL? [duplicate]

When I prove some language is context free, It is too hard to find example string. Is there any tips? It takes too many time or eventually give up.
1
vote
1answer
32 views

How to prove that a language is not context-free using pumping lemma

I'm trying to prove that that language isn't a context free: $ L = \{ w11w \mid w\in \Sigma^* = \{0,1\}\}$ I succeed to prove that $L = ww$ isn't context free, but not the language above. What ...
0
votes
0answers
19 views

How to prove this language is not context-free language by pumping lemma? [duplicate]

Could I get help to prove that the language $\{a^i b^j c^k \mid i>j>k\ge 0\}$ is not context free language by using pumping lemma?
1
vote
1answer
44 views

Is this language is Context-free language or not?

Is anybody can help me please to determine is this language is Context-free language or not? L={wvw | w,v∈{a,b,c}+} for example: part of the language: acbac, abcab, bbcbb not part of the language:...
1
vote
0answers
12 views

Context free/Non Context free Language [duplicate]

Let L = { uv composed of {0,1} | |u| = |v| and u = v } Do we agree that this language is not a Context Free Language ? If not, why ? Can you give me a pushdown automata that recognizes it or the ...
3
votes
2answers
43 views

Can the pumping lemma for context free languages be extended to any subword?

It is known that in the case of a Regular Language $L$ , the pumping lemma can be extended to apply to any sufficiently long subword of the language, ie, if $uwv \in L$ and $|w| \ge p$ then we can ...
-1
votes
1answer
65 views

How construct PDA to $L = \{x \in(a,b,c,d)^* \mid -10 \leq ( |x|_a + |x|_b) - ( |x|_c + |x|_d) \leq 10 \}$

$L = \{x \in(a,b,c,d)^* \mid -10 \leq ( |x|_a + |x|_b) - ( |x|_c + |x|_d) \leq 10 \}$ I don't have any idea. Can someone help me.
0
votes
1answer
105 views

Prove $ L = \{ww^{R} \in \{a, b\}^{*} : |w|_{a} \equiv |w|_{b} \equiv 0$ $ (mod$ $13) \} $ is regular or context-free or neither

$ L = \{ww^{R} \in \{a, b\}^{*} : |w|_{a} \equiv |w|_{b} \equiv 0$ $ (mod$ $13) \} $ Exercises: If the language L is regular (build a DFA or regular expression) else if the language L is context-...
5
votes
2answers
916 views

Pumping lemma: if you can keep pumping, what does this tell you?

Hypothetically, let's say you are using the pumping lemma for either regular or context free languages. Now using either, you come across a case that remains true despite pumping it. In this situation,...

15 30 50 per page