Questions tagged [context-free]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
21 views

DFA and RE find out the language. Please can you explain?

Find the regular expression describing following languages over alphabet {0, 1}*. ...
0
votes
1answer
34 views

Formal proof of existence of equivalent parse tree for each derivation

Where I can find formal proof of there exists an equivalent parse tree for each derivation? There is a lot of informal proof of equivalency on the internet but I need formal proof to reference it in a ...
4
votes
0answers
52 views

How to prove that the problem $\text{"If $L$ is a context-free language, then, is $\overline{L}$ also context-free?"}$ is undecidable?

Lately I came across a problem: $\text{"If $L$ is a context-free language, then, is $\overline{L}$ also context-free?"}$ And I need to comment on its decidability. Now I know that context free ...
0
votes
1answer
45 views

How to use pumping lemma on languages that do not follow a strict structure?

Let me preface this by saying, I do NOT want an example of a proof, I would merely like pointers as to how I could approach this problem. For example, I have a language: $$L = \{w \mid w \in \{0, 1\}^*...
0
votes
1answer
42 views

Can a grammar that has only one leftmost derivation tree for every sentence, have more than one rightmost derivation tree for some sentence?

I'm currently studying the book Engineering a Compiler by Keith Cooper, and in chapter 3, there is the following definition: A grammar G is ambiguous if some sentence in L(G) has more than one ...
1
vote
1answer
27 views

Test whether words of less a's than b's or c's but not at the same time is context-free

I want to test whether $L= \{w\in\{a,b,c\}^* \mid |w|_a<|w|_b \text{ or } |w|_a<|w|_c,\text{ but not at the same time} \}$ is CFL or not (I assume not), but I am struggling to do so. The closest ...
1
vote
0answers
29 views

Algorithm for transforming all left-recursive rules in a grammar into direct left-recursive

I'm probably missing a lot of terminology here, so I'll try to rather be too clear than too vague. I have a Context-Free grammar as an input, that might contain direct or indirect left-recursion ...
2
votes
2answers
86 views

Why {${xww|x,w∈(a+b)^*}$} is regular but {${ww|w∈(a+b)^*}$} is not $? $

I read this site example 12 that {${xww|x,w∈(a+b)^*}$} the set of strings generated by language $L$ is {${ϵ,a,b,aa,ab,ba,bb,aaa,…}$} by taking always $w$ as $\epsilon$ and $x$∈$(a+b)^∗$. But my ...
3
votes
1answer
65 views

Context free grammar for strings with more $a$'s than $b$'s

I would like to prove that the grammar $G$ with the rules $$ S \to SS \mid aSb \mid bSa \mid a \mid \varepsilon $$ generates the language $L = \{w \mid \text{$w$ has at least as many $a$'s as $b$'s}\}$...
0
votes
1answer
70 views

Details wanted on the reduction from Circuit Value to CFG Membership

Consider a Boolean Circuit $C$ which takes $n$ inputs and has one output. Notation: Let $\textit{size}(C)$ be the size of circuit $C$: the total number of gates in $C$. Let $G = (V,\Sigma,R,S)$ be a ...
1
vote
3answers
64 views

A non-CFL over {a,b,c} with a non-CFL complement?

I understand uncountably many such languages exist, and the rational for it is clear to me. I just can't think of one trivial, easy to prove example. For instance, the complement of a^nb^nc^n is CF, ...
-3
votes
1answer
47 views

Designing a context free grammar for a language

Design a grammar for the language $$F = \{x^a y^b zx^b y^a\mid a, b\geq 1\}$$ I'm trying to get a stronger grasp of designing grammars for languages. A thorough explanation of how to design the ...
1
vote
1answer
49 views

Give a context-free grammar

We know that $L$ = { $w$ $\in$ {a, b}* $|$ $|w|_{a}$ > $|w|_{b}$ } This is my answer: $G$ = ({$S$,$A$,$B$},{$a$,$b$},$R$,$S$) $R$ = S $\to$ $AB$ $A$ $\to$ $aA | Aa |B$ $A$ $\to$ $a | abB | Bab | ...
0
votes
0answers
56 views

Proving that $\{ a^i b^j c^{\max(i,j)} \}$ is not context-free

Prove that $L$ is not a Context-free language, where $$L = \{ a^{i} b^{j}c^{h}\mid i,j,h\in \mathbb{N} \wedge h = \max(i,j)\}.$$ I have an idea: It can be divided into two situations: When $i < j$...
1
vote
0answers
37 views

In what sense is a CFDG grammar a context free grammar?

CFDG is described as a language for context free grammars which can generate images. It allows rules to have parameters, but places restrictions on them to ensure the grammar is context free rather ...
0
votes
1answer
44 views

Is $B=\{a^n b^m \mid n \not= 2m\}$ a context free grammar [duplicate]

I was trying to find a grammar that generates $B=\{a^n b^m \mid n \not= 2m\}$ but I couldn't so I'm not sure that it is a CFG. This is what I did : $$ S\rightarrow X \mid aX \mid a \mid b \mid \...
1
vote
1answer
40 views

Proof of an interesting language being non-context free

Let $\Sigma = \{a, b, c\}$ and $L = \{wa^{1 + k + 2n}b^nw^{rev}\mid n, k \in \mathbb{N}_0, w \in \Sigma^*\}$. It is clear that $L$ is context free, but the question is the following: Let $L'$ be the ...
0
votes
1answer
54 views

What's the Context-Free grammar of this language : $L= \{a^n b^m c^p d^q |m+n=p+q, n,m,p,q \geq0 \}$ [duplicate]

I was trying to find the context-free grammar of `$L= \{a^n b^m c^p d^q |m+n=p+q, n,m,p,q \geq0 \}$ but I'm stuck. This is what I did so far: $$ S \to X S Y | \lambda$$ $$X \to a|b$$ $$Y \to c|d $$ ...
1
vote
2answers
57 views

If $p(n) := \sum_{i=0}^ka_in^i$ where $a_i\in\mathbb{N}, a_k \ne 0$ AND $k \ge 2$, is $L = \{0^n1^{p(n)} \mid n\in\mathbb{N}\}$ context-free?

I have the really strong feeling it is indeed NOT context-free, since the language $1^{n^k}$ for $k\ge 2$ is not context free (proven by the pumping lemma) and, in a sense, "the order of ...
1
vote
1answer
55 views

Is $(L_1^c \cup L_2^c)^c$ context-free or context-sensitive

I came across the following question: Let $L_1$ be a regular language and $L_2$ be a context-free language. Let $L_1^c$ and $L_2^c$ be their complements respectively. What can be said about $(L_1^c \...
9
votes
2answers
322 views

What is the closure of context-free languages under finite intersections?

Famously the intersection of context-free languages need not be context-free. On the other hand the intersection of context-sensitive languages is context-sensitive. So this leads to the question: ...
1
vote
1answer
58 views

Is $L = \{xw^3x^{rev}\mid x, w\in\{0, 1\}^*\}$ context-free?

The title pretty much explains the question, but still: Is the language $$L = \{xw^3x^{rev}\mid x, w\in\{0, 1\}^*\}$$ context-free? I think it isn't and would motivate that suspicion by the following ...
-2
votes
3answers
73 views

Context-free grammar for $a^{2n} b^{2n}$

I have just started learning formal languages and here is a question I am facing a little hurdle: Construct a context-free grammar for $\{ a^{2n}b^{2n} \mid n \ge 0 \}$. This was what I got at first....
0
votes
1answer
25 views

Does this grammar accept this words?

I made this grammar: $S \rightarrow ASa$ $S \rightarrow c$ $A \rightarrow a|b$ And I want to check that it accepts words like $aacaa$, $abcaa$, $babcaaa$, I formed the grammar by thinking about the ...
1
vote
1answer
30 views

Decidability of $\{⟨G⟩ \mid \text{$G$ is CFG and $L(G) ⊈ \Sigma^+$}\}$

I want to prove that the following language is decidable: $$\mathit{SEQ}_{\mathit{CFG}} = \{⟨G⟩ \mid \text{$G$ is CFG and $L(G) ⊈ L$}\}, \text{ where } L = \Sigma^* - \{\epsilon\}$$ So, I think about ...
0
votes
0answers
15 views

Check if a language is context free [duplicate]

Check whether the following language is context-free. If yes, a suitable grammar should be given; if no, the pumping lemma should be used as a tool. $$L=\{a^ib^jc^k \mid i, j, k \in N \text{ and } i &...
0
votes
1answer
67 views

Proof that $\{a^ib^jc^k\mid i,j,k\in\mathbb{N}, i<k<j\}$ is not context-free using the Pumping Lemma

$$ L=\{a^ib^jc^k \;| \;i, j, k \in \mathbb{N} \; \text{and} \; i <k<j\} $$ I need to show that this language is not context-free with the help of the Pumping Lemma. My first intuition is, that ...
0
votes
0answers
16 views

Context Free Grammar to Chomsky Normal Form Help

I am trying to convert the following CFG to CNF: S -> ABS | ε A -> BSBa | a B -> Ba | a The finally result looks like this: ...
0
votes
0answers
37 views

pushdown automata question

We define a new model: A "100-PDA" is a pushdown automaton with at most 100 states and with at most 100 symbols in the stack alphabet. Prove or disprove the following statement: "There ...
0
votes
0answers
32 views

Grammar for all words $0^n1^m$ such that $n \ge m+2$

Given grammar $$L(G) = \{ 0^n1^m | n \ge m + 2 \}$$ What is the grammar for this? I know the grammar for the following language: $$ L(A) = \{ 0^n1^m | n = m + 2 \} $$ We can divide any string in $L(A)$...
0
votes
0answers
19 views

Importance of strings of length less than or equal to $2^{V+1}$ generated by a grammar in CNF , where V is number of non terminal symbols?

I have this question: prove that the problem of testing whether a Context free grammar generates some string in $1^*$ is decidable. I know one way to prove it. But I saw a different way of its proof ...
0
votes
0answers
16 views

non-ambiguity of DCFG [duplicate]

Show that every Deterministic context free grammar is an unambiguous context free grammar How can I show this ? can anyone give a proof?
1
vote
2answers
58 views

What is appearance checking in the context of formal grammars?

As I did not find any definition of the term "appearance checking" although it is widely used, I am eager to ask as what it can be defined. Perfect would be an example using a context free ...
1
vote
1answer
39 views

Is the concatenation of a non-regular CFL and a complement of a regular upper-set always non-regular?

Let $L_1$ be a non-regular CFL. Let $L_2$ be a regular language. Assume that $\left(L_1\right)^{*} \subseteq L_2$. I'm looking at $L_3 = \left( L_1 \right) ^{*} \circ \overline{L_2}$. Is $L_3$ always ...
1
vote
2answers
49 views

Is there a grammar for this language? $w^{m-1}aca^m$?

I have to form a free context grammar for this language $w^{m-1}aca^m$ where $w \in \{a,b\}$, so what I have been able to do is this: $X \rightarrow SacA$ $S \rightarrow aS|bS$ $A \rightarrow aA$ But ...
0
votes
1answer
25 views

Pushdown automaton with binary stack

I have a problem where I'm asked to prove that if P is a pushdown automaton, then there exists another pushdown automaton P' with only two symbols in its stack alphabet that accepts the same language ...
0
votes
1answer
31 views

How to demonstrate unambiguous CFG and CNF?

I have to show that if G is an unambiguous CFG, the transformed grammar G' in CNF is also unambiguous. But couldn't come up with something concrete. I could only visualize the case where the grammar G ...
1
vote
0answers
32 views

Unambiguous formal grammars for a specific class of languages

Suppose that $w \in \{0; 1\}^*$ is a binary word. Let's denote the number of $0$-s in $w$ as $\#_0(w)$ and the number of $1$-s in $w$ as $\#_1(w)$. Now suppose that $q \in \mathbb{Q}$ is a positive ...
0
votes
1answer
34 views

Pumping Lemma for $\mathcal{L} = \{ \omega \omega^R a^{|\omega|} : \omega \in \{a,b\}^* \} $

I have to show that this language is not context free $\mathcal{L} = \{ \omega \omega^R a^{|\omega|} : \omega \in \{a,b\}^* \} $, where the $R$ corresponds to the reverse. For this I will use the ...
0
votes
0answers
38 views

Designing CFG that accepts $a^n b^m c^p$ where $n=m+p+2$

I have generated the CFG of $a^n b^m c^p$ where $m = n+p+2$: $S \rightarrow ASC \mid \varepsilon$ $A \rightarrow aAb \mid \varepsilon$ $C \rightarrow bCc \mid \varepsilon$ I have been trying $a^n b^...
0
votes
0answers
27 views

Prove $L =\{0^{2^n}\mid n \geqslant 0\}$ is not context free [duplicate]

Here $0^j$ means $0$ repeated $j$ times e.g. $0^2$ is $00$. So to prove this I was asked to use the pumping lemma. So let $m$ be the pumping length and assume $L$ is a CFL by contradiction. We can ...
-2
votes
1answer
49 views

CFG for $\{uvw \mid u,v,w \in\{0,1\}^*,|u|=|v|=|w| \wedge u\neq w\} $

$L=\{uvw \mid u,v,w \in\{0,1\}^*,|u|=|v|=|w| \wedge u\neq w\} $ Any help would be appreciated.
1
vote
1answer
24 views

How to design a turing machine for a context-free grammar? what are the steps?

How to design a Turing machine for a context-free grammar? what are the steps? for example, What are the steps to design a Turing machine for the following grammar with alphabet $\{a,b\}$. $S\...
1
vote
1answer
38 views

Context-free grammar for $a^ib^ic^id^{3i}$

I'm trying to make a context-free grammar for $L=\{a^ib^ic^id^{3i}\mid i>0\}$. I could make a grammar for $a^ib^jc^jd^{3i}$. But I can't make the grammar for the special case that $i=j$ as it is ...
1
vote
1answer
47 views

Proving $\{ a^n b^m \mid n \leq m^2 \}$ is not context-free using pumping lemma

I am working on a pumping lemma question and trying to prove that the following is not context-free, but I can't finish the proof. The language is $$L = \{ a^n b^m \mid n \leq m^2 \}$$ Assume Demon ...
0
votes
1answer
33 views

Context-free language from grammar

I'm on second year IT studies. I can't do this on my own and my teacher is not eager to help. I went that way but I'm pretty sure it's wrong. Please, help :/
1
vote
1answer
44 views

Context-free grammar for complement of $\{ab \mid b=\mathrm{complement}(a)\}$

I want to construct a context-free grammar for $$L=\Sigma^*-\{ab \mid b=\mathrm{complement} (a) , a,b \in \{0, 1\}^*\}$$ and prove the correctness of answer. The complement of a string is obtained by ...
0
votes
0answers
37 views

Prove with pumping lemma that the language { $a^n b^n b^m a^m | n ≠ m $ } is not context free

I'm having a trouble proving it to be non-context-free. For example, if I take w = $a^k b^k b^{k+1} a^{k+1}$, it would be problematic if the partition of $vxy$ with $|v| = |y|$ was in the $ b^{k+1} a^{...
1
vote
0answers
45 views

Checking correctness of grammar for $L = \{w \in \{a, b\}^* \text{ }| \text{ } w \text{ has } n_a(w) = 2n_b(w)\} $

I have written a CFG that supposedly generates $L$ below. $$L = \{w \in \{a, b\}^* \text{ }| \text{ } w \text{ has } n_a(w) = 2n_b(w)\}$$ Where $n_a(w)$ is the number of $a$'s in $w$ and similarly for ...
0
votes
0answers
21 views

Eliminating left recursion using a loop construct

I'm trying to merge a little bit of theory with a little bit of practice. I'm writing a parser-generator that generates a top-down parser based on a given grammar. I'd like to handle left- and right ...

1
2 3 4 5
30