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
1
vote
1
answer
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
0
answers
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
2
votes
1
answer
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 ...
- 21
2
votes
1
answer
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
3
votes
1
answer
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 ...
0
votes
1
answer
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'...
0
votes
2
answers
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
0
votes
1
answer
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 ...
- 305
3
votes
2
answers
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
0
votes
1
answer
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 ...
- 305
8
votes
1
answer
730
views
Conjecture: a half of a pairing context-free language must be a regular language
If $A$ and $B$ are languages, let $A\bowtie B$ denote the set of strings made by concatenating any word from $A$ and any word from $B$ of equal length.
$$A\bowtie B \equiv \{ ab : a\in A,\;b\in B, |a|=...
- 758
0
votes
1
answer
116
views
Decidability of a context free Grammar
Say that a Context Free Grammar is red when it accepts every word of length 3 that begins with a, and extremely red when it accepts every word that begins with a.
Is redness decidable? or Semi ...
- 1
2
votes
1
answer
201
views
Prove/find context free grammar is unambiguous for the language $L$
I am trying to find a grammar and prove that it is unambiguous for the language $L$, where $$L = \{ w \in \{a,b\}^+; |w|_a = |w|_b \} $$
Essentially: word $w$ contains at least one $a$ and $b$; where ...
- 23
2
votes
2
answers
805
views
Context free grammar for a language that is a complement of another
Create a context free grammar for L.
$$ L=\{a^nb^mc^k | n+m \neq k\} $$
First I tried to create a CNF for a language that accepts strings in which $n+m = k$. I got this:
$$
S \rightarrow aAc
$$
$$
A \...
- 61
0
votes
1
answer
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
0
votes
1
answer
56
views
Context-free pumping lemma of $a^nb^n$
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
3
votes
1
answer
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
1
answer
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
0
answers
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
1
answer
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 ...
- 13
0
votes
1
answer
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
0
votes
1
answer
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 ...
0
votes
1
answer
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
0
votes
1
answer
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
...
0
votes
1
answer
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
3
votes
0
answers
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
2
answers
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
1
answer
322
views
Why is $a^mb^nc^pd^q$ with $m+p=n+q$ context-free?
$L = \{$$a^mb^nc^pd^q \mid m+p = n+q,$$\text{ where } m, n, p, q \geqslant0\}$
If, for instance, we try to construct a PDA for a similar language
$L2 = \{$$a^mb^nc^pd^q \mid m=p $ $\text{and}$ $ n=q,$$...
- 133
0
votes
1
answer
49
views
How to prove correctness of a bidirectional converter between two CF grammars?
I have a converter between two context-free grammars which are both describing the same language but one uses infixes other than prefixes, has different symbols and sometimes switches order of ...
- 129
1
vote
1
answer
318
views
If the Pushdown-Automaton for a language is deterministic, is the language non-ambiguous?
For a given context-free grammar (CFG) you can always construct a pushdown automaton PDA (and vice-versa). This pushdown automaton is possibly non-deterministic, since for a non-terminal $X$ in the ...
- 29
0
votes
0
answers
142
views
How to count the number of nodes for a tree generated by context free grammar derivation?
Given context free grammar I use breadth first search and left most derivation rule to generate all possible words for a given language.
For example:
...
- 299
-1
votes
1
answer
33
views
Can I use the CYK-Algorithm for a Grammar where all results still have a Variable in them?
Let the Grammar be G = ({S}, Σ, P, S), where Σ = {⟨,⟩,[,]} and
P: S → ⟨S⟩, [S], SS, ε
[⟨ → ⟨[
Can I still use the CYK-Algorithm and if yes then how would I do it ...
- 27
0
votes
1
answer
422
views
Disambiguating grammar for Dyck language
Given the following simple grammar for a language that contains all strings with matched parentheses:
\begin{align}
&s \to ss \\
&s \to (s) \\
&s \to ()
\end{align}
Examples: $(), ()(), (()...
- 299
0
votes
1
answer
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'...
0
votes
1
answer
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
2
answers
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 ...
0
votes
1
answer
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
0
votes
0
answers
149
views
Decidability of the language of a regular expression being a subset of a given context free language
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, ...
- 11
1
vote
1
answer
40
views
Is there a way to show that if the description of a language depends on some kind of global structure, then it isn't a CFL?
So I've been reading Sipser's theory of computation book, and I've come across the pumping lemma for context-free languages, which as a reminder says that if a language is context-free, then there is ...
- 147