Questions tagged [context-free]

Questions about the set of languages (equivalently) described by context-free grammars or accepted by (non-deterministic) pushdown automata.

1,681 questions
Filter by
Sorted by
Tagged with
1 vote
535 views

Context-free grammar for $L=\{ a^nb^m | n \le m+3 \}$

I'm having problems determining the productions for a CFG describing the language $L=\{ a^nb^m | n \le m+3 \}$ where $n,m \ge 0$ I'm very new to this so this example might be a little harder, but ...
• 167
1 vote
225 views

Relation between left derivations, right derivations and number of parse trees?

I saw this question on a test-prep site Given a CFG and a string, what is the relation between the number of leftmost derivations, the number of rightmost derivations and the number of parse trees? ...
• 275
122 views

prove that if L is context-free then L' = {w2#w1 | w1#w2∈L} is context-free

Given that $\#\notin \Sigma$ and $L\subseteq \Sigma^*\#\Sigma^*$, prove that if $L$ is context-free language then $L' = \{w_2\#w_1 \mid w_1\#w_2\in L\}$ is context-free. I'm trying to prove this in ...
50 views

Find a context-free grammar for uc^nd^nv where the number of a's and b's in uv are equal

I want to construct a context-free grammar for this language: \begin{align*} L = \{uc^nd^nv\mid \ u,v \in \{a,b\}^* \text{ and the number of a's and b's in } uv \text{ are equal}\} \end{align*} I know ...
• 23
62 views

Is there an alternative for the formal language theory that could be used for flowchart diagrams?

I am creating a tool for validating, parsing, and interpreting flowchart diagrams on diagrams.net, and it is necessary to give users an opportunity to define a set of rules for the diagram. So, in the ...
106 views

Construction of a Turing Machine that accepts the language of (a^nb^nc^md^m for) m,n >= 1

i recently have been practicing constructing Turing Machines for languages. But i can't seem to figure this one out. I've seen a few videos on constructing 3 equal length strings (a^nb^nc^n) But i can'...
863 views

How do we check $x ≠ y$ in $PDA$ for $L = \{xy | x, y \in (0 + 1)^*, |x| = |y|, x ≠ y\}?$

We know that $L = \{ xy | x, y \in (0 + 1)^*, |x| = |y|, x≠y\}$ is context free. But my question is how we check $x ≠ y$ in $PDA?$ For example $x=0^n1^n$ and $y=1^{2n}.$ We can easily draw $PDA$ by ...
• 346
739 views

How to prove ww^r is context free using pumping lemma for context free languages

I am having a hard time to prove it, what i know is we cannot prove that a language is regular by using pumping lemma cause even if the "pumped string" is in the language the language could ...
1k views

Is this language a context-free language or not?

I try to determine if the following statement is true: for any given language $L \subseteq A^*$ if $L$ is a context-free language then $L_1 = \{u^Rv^R \ | \ uv \in L, |u|=|v| \}$ is also a context-...
• 55
927 views

When is a grammar ambiguous or When is a grammar not ambiguous?

I was looking at an example of grammar from the website: grammer example which is as follows: S → aB / bA S → aS / bAA / a B → bS / aBB / b I believe they forgot to write: A -> a Next, we are going ...
730 views

• 61
112 views

prove or give counterexample about regular language

Let $\Sigma = \{a,b\}$, $L_1,L_2\subseteq \Sigma^*$ $L_1 ◃ L_2 = \{w∈ \Sigma^* | \exists v\in L_1, vw \in L_2\}$ For any context-free language $L$, regular language $R$, whether $L \triangleleft R$ ...
• 193
56 views

I know $a^nb^n$ with $n\geq0$ is considered a context-free language, but if I try: Using pumping length $p = 3$ $n = p$, thus we have $aaabbb$ $u =aa$ and $y = bb$ $v = a$, $w = b$ and $x=λ$, then $|... • 105 1 vote 0 answers 24 views Prove that$L=\{a^ib^jc^k\ |\ i\neq j,\ i\neq k,\ j\neq k\}$satisfies the pumping lemma [duplicate] I've faced this question while I was solving some past homework and I couldn't really figure out how I would solve it. Question: Prove that$L=\{a^ib^jc^k\ |\ i\neq j,\ i\neq k,\ j\neq k\}$satisfies ... • 453 2 votes 0 answers 25 views Finding a Context Free Grammar for Different No. of a and b AND Different No. of b and c [duplicate] The question is from my homework: Is the language$\{a^ib^jc^k\mid i,j,k\geq0\land i\neq j \land j \neq p\}$a context-free language (CFL)? If yes, please provide a context-free grammar for it. I ... 0 votes 1 answer 191 views Finding a context free grammar (CFG) for a non-context free language (CFL) a^n b^n c^n It is known that the language$\{a^nb^nc^n|n\geq0\}$is not context-free (we can prove it using the pumping lemma, as shown here: Is$a^n b^n c^n$context-free?). Yet, this answer claims it has found ... • 1 1 vote 0 answers 648 views Prove that determining if a PDA has an infinite language is decidable I have been given the following problem and was wondering if my solution is correct (taken from the textbook exercise in the book Introduction to the Theory of Computation by Martin Sipser): Given $$\... • 181 1 vote 0 answers 49 views Prove that the problem of CFG producing epsylon is decidable I have been given the following problem and was wondering if my solution is correct (taken from the textbook exercise in the book Introduction to the Theory of Computation by Martin Sipser): Given$$\... • 181 0 votes 1 answer 59 views Is the intersection of any context free language and the set of all palindromes context free? Let$L$be any context-free language. Is the set of all palindromes that are elements of$L$also context-free? I know that the intersection of context free languages isn't guaranteed to be context ... • 423 4 votes 2 answers 932 views How to show that the NECESSARY_CFG is Turing-recognizable but undecidable? I have been given the following problem and was wondering if my solution is correct: Say that a variable$A$in CFG$G$is necessary if it appears in every derivation of some string$w$where$w$is ... • 181 0 votes 1 answer 64 views Find non CFL$L$such that Pref($L$) is CFL While studying I've encountered this question written above. I am familiar to the closure properties of CFL, and even know that $$L=\{a^{j^2}|j\geqslant 0\}$$ ($a$to the power of ($j$to the power of ... 1 vote 1 answer 122 views Show the pumping lemma is not a universal method for proving not context-free I know that the pumping lemma is not powerful enough to prove a language is not context-free, but I don't understand how to show it. I have the same question as this one Show that the Pumping Lemma ... • 13 1 vote 2 answers 97 views Prove that$L=\{0^n1^{n+1}\ |\ \exists k\in \mathbb{N} :\ 4n+2=6k \}$is CFL I've faced a question in my homework, I was able to solve it but not as desired. Question: Given the language$L=\{0^n1^{n+1}\ |\ \exists k\in \mathbb{N} :\ 4n+2=6k \}$, Prove that it's a CFL (Note: ... • 453 1 vote 1 answer 294 views Prove/Refute that$L=\{w\$x^R \ |\ x\ is\ a\ substring\ of\ w\}$ is a regular language

I was solving some exercises about CFL from past years' homework and faced this question. Question: Given the language $L=\{w \# x^R \ | \ x\ is\ a\ substring\ of\ w\}$, prove/refute if it's regular ...
• 453
950 views

Is $a^nb^mc^k$, $n\neq m$ and $m\neq k$ context-free?

Is the language, $a^nb^mc^k$, where $n\not=m$ and $m\not=k$ in CFL or not? When the condition is changed to $n\not=m ~\|~ m\not=k$, it can be shown that the language is the union of 2 CFLs. However ...
• 275
1 vote
254 views

Context-free grammar for $\{1^i0^j1^k \mid i+2j=k\}$

Suppose $$L=\{1^i0^j1^k\mid i+2j=k\}$$ How can I construct a context-free grammar for $L$? This is homework. Here is my attempt for the case when $L$ is defined with $i+2j=3k$ instead. \begin{align*} ...
• 83
1 vote
18 views

Produce a CFG for $\{a^ib^j \mid i<j\}$ [duplicate]

How do I go about producing the context-free grammar for something like $\{a^i b^j \mid i<j\}$? If it was $i=j$, then it's simple. But for something like this, is there a process to achieve it, or ...
• 19
1 vote
44 views

How does this context-free grammar generate even length strings on either side?

I came across this context-free grammar for the language L = {xy||x|=|y|, x≠y}, but I can't seem to see how it can generate all lengths for x and y. Could someone illustrate this? For example, how ...
386 views

Intersection between CSL and CFL?

I am trying to find a proof of A ∩ B where A is a CSL and B is a CFL. Also I know that CFL is a strict subset of CSL. Does that mean that their intersection will give CFL. I am stuck
93 views

Intersection of Infinite Regular Language with CFL

Intersection of any finite regular language with anything( CFL or not CFL) will be finite but what about intersection of infinite regular language with CFL or not CFL. Does the resultant will be ...
75 views

How would my parsing functions look for this grammar?

Suppose we have the grammar $$S \to aA | BA$$ $$A \to a | bB | \epsilon$$ $$B \to cB | d$$ I know that I need to write four different functions in order to parse this grammar. They are ...
• 3
79 views

What could be possible NFA for the RegEx "a?"

I am trying to use the Thompson's method to draw an NFA for a RegEx given by: $(a+b|c?)c$ I am wondering if I should deconstruct the RegEx as - Concatenation of $a+$, $(b|c?)$ together with $c$ OR ...
45 views

Why do non Context Free languages need more stacks?

In an example question sheet for my exams our professor included “Know to explain why for non CF languages 1 stack is not enough.” We haven’t delved into CS and reclusively enumerable languages much ...
• 225
30 views

Is there a context-agnostic concept of automatic (log-)text parsing that supports human reader filtering out redundancy?

This question is about ideas I regularly think about, and I would like to know what concepts already exist. Also I am not sure at all if this really makes sense, by now it is just a crazy idea ...
• 131
1 vote
3k views

Proving the grammar S → SS+ | SS∗ | a is unambiguous

Consider the context-free grammar G = ({a, +, ∗}, {S}, {S → SS+ | SS∗ | a}, {S}) and consider the string aa+a* generated by this grammar. Is this grammar unambiguous? I have browsed the Internet and I ...
• 127
1 vote
322 views

• 299
730 views

Show that if L is CFL and R is a regular language then {w ∈ Σ^∗ | xw ∈ L for some x ∈ R} is context free

Show that if $L$ is CFL and $R$ is a regular language such that they both share the same input alphabet $\Sigma$, then $C = \{w \in \Sigma^*\mid xw \in L$ for some $x \in R\}$ is context free. Hi I'...
638 views

Remove left recursion from a grammar without necessarily removing epsilon production

Consider the grammar $$S →Aa∣b$$ $$A →Ac∣Sd∣ϵ$$ Construct an equivalent grammar with no left recursion and with minimum number of production rules. $\tag {GATE-CS-1998}$ While solving this question, ...
• 1,112
1 vote
205 views

Are there any algorithms that decide if a PDA (pushdown automaton) accepts a sentence?

Most computation theory textbooks just mention the equivalence of PDAs and Context Free Grammars. I'm able to construct a PDA from a given CFG, but find it very difficult to write an algo to check if ...
36 views

Prove that $L =\{ a^n b^m c^{n\times m} \mid n, m\geqslant 0\}$ is not context free

I looked at all possible options for $vx$ when you look at $z = uvwxy$ and can't find a contradiction in the case where $b$'s and $c$'s are in $vx$.
• 11
Let L be a language of pairs $\langle R,G\rangle$, with the first element being a regex and the second being a CFG. Is it decidable that G accepts whatever the regular expression does? In other words, ...