People who code: we want your input. Take the Survey

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
1answer
21 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
26 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
13 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 &...
-2
votes
0answers
34 views

Context free grammar to chomsky normal form bruh

I've had this question bugging me for so long but i cant seem to solve the question can anyone help? S 🡪 [ R ] R 🡪 [ Q ] | T T 🡪 j R | ε Q 🡪 i k | ε
0
votes
1answer
56 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 ...
-1
votes
0answers
47 views

Remove grammar ambiguity

I want to remove the ambiguity from the following grammar: X->aX|YXc|c|ε Y->bZ|ε Z->XYa
0
votes
0answers
13 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
35 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
29 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
13 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
53 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
37 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
45 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
23 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
16 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
28 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
22 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
37 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
24 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
46 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
36 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 ...
-3
votes
0answers
28 views

Does the String belong to the language

Down here below I have a context-free grammar in BNF form. Does the string "a.b.c.d" belong to the language defined by this grammar? I think it does because of the rule ...
-2
votes
0answers
19 views

Relationship between Context-Free Grammar and Compilers

Summarize the relationship between context-free grammars and compilers for general-purpose programming languages. Is a question from an old exam? Is that the Context-free grammars decide the grammar ...
1
vote
1answer
43 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
32 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
42 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
28 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
44 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
18 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 ...
0
votes
1answer
27 views

CFG and PDA for the set of strings in $\{a, b, c\}^∗$ such that the number of b’s is equal to the sum of number of a’s and c’s

I'm trying to find the CFG and PDA for the above language. I have so far come up with this $S \to S_1S_2 \\ S_1 \to aS_1b \\ S_2 \to bS_2c$ However, I realized that this is just a subset of the ...
0
votes
0answers
21 views

Finding the language of a given CFG

I'm trying to find the language of the given CFG $S \to aB \mid bA \mid a \\ A \to bAA \mid aS \\ B \to aBB \mid bS$ I understand that the productions $S \to aB, S \to bA, A \to aS$ and $B \to bS$, ...
0
votes
0answers
27 views

Construct a PDA that recognizes $L = \{w : w \neq a^n b^n : n ≥ 0\}$

I'm trying to find the PDA of the above language. I understand that this is the complement of the language $L_1=\{w : w=a^nb^n : n\geq0\}$ However, I can't understand the idea behind constructing the ...
1
vote
1answer
62 views

eliminate left recursion of below grammar

Please look at this grammar: $$𝑆 → 𝑆𝐴𝐵 \ | \ 𝐴𝑏 \ | \ 𝑏 \\ 𝐴 → 𝑆𝐵 \ | \ 𝑎 \ | \ 𝐵𝑆 \\ 𝐵 → 𝐴𝑆 \ | \ d$$ I eliminated B from the grammar and it converted to: $$ S → SAAS \ | SAd \ ...
2
votes
4answers
95 views

Proving that $L=\{ w \mid \lvert w \rvert$ is prime $\}$* is a regular language

I'm trying to prove that the following languague is a regular language: $L=\{ w \mid \lvert w \rvert$ is prime $\}$* What I have thought is to divide each word $w \in L$ into subwords of length 2 if ...
1
vote
1answer
34 views

Create a CFG for $L = \{ a^ib^j \mid \lvert i - j \rvert \le 2 \} $

I'm trying to find a CFG for the following language: $L = \{ a^ib^j \mid \lvert i - j \rvert \le 2 \} $ What I thought about unsuccessfully is the following: $S \rightarrow SASBS \mid SBSAS \mid \...
1
vote
1answer
28 views

Closure of context-free languages under left-half [duplicate]

The regular languages are known to be closed under the operation "left half": $$ \operatorname{left}(L) = \{ x \in \Sigma^* : xy \in L \text{ for some } y \in \Sigma^* \text{ s.t. } |x|=|y| \...
3
votes
1answer
60 views

Existence of a CFL $L$ such that $\sqrt{L}$ is not CFL

Does there exist a CFL L such that the language defined as $L' = \sqrt{L} = \{w | ww \in L\}$ is not CFL? I feel that there is no such $L$ but obviously, I am unable to prove it. I am sorry but I have ...
1
vote
2answers
51 views

Proving that a language is a CFL

Assume that $L_1 \subseteq \Sigma^*$ is a CFL and that $y \in \Sigma^∗$ is a string. I need to prove that the language $L_2 = \{x \in L_1 \mid x \text{ does not contain $y$ as substring}\}$ is a CFL. ...
2
votes
1answer
47 views

Construct PDA for $Σ^* -\{(a^nb) ^n, n>0\}$

I want to construct a PDA for $Σ^* -\{(a^nb) ^n, n>0\}$ where $Σ=\{a, b\}$. Here is my try: I know that context-free languages are closed under union operation. Also I know how to make a PDA for ...
0
votes
1answer
23 views

Context free grammar transformation to Normal Form

I found a task where you need to transform context free grammar to normal form. I'm a High Shcool student at this moment. But my Brother learning this at the university. He don't have much time to ...
-2
votes
1answer
13 views

Showing that $K$ is dedicable is equivalent show that $Acc_{GNC}$ is decidable

If $K$ is a context-free language, then $K$ is a decidable language. $\text{Acc}_{\text{CFL}} = \{〈G, w〉: G \text{ is a context-free grammar and G can generate } w\}$ is decidable. I am a bit ...
0
votes
1answer
36 views

Grammar for $\{a^n b^n c^m d^m \mid n \geq 1, m \geq 0\}$

I'm trying to understand how the construction of simple grammars works. In my textbook, there's the following example I am supposed to find a grammar for: Let $L_1= \{a^n b^n c^m d^m \mid n \geq 1, m ...
2
votes
2answers
63 views

Infinite prefix-closed context-free languages contain an infinite regular subset

The Problem: Say that a language is prefix-closed if all prefixes of every string in the language are also in the language. Let C be an infinite, prefix-closed, context-free language. Show that C ...
3
votes
1answer
745 views

Can a language be context free and not have a BNF grammar?

Leslie Lamport claims that TLA+ is too complex to be described in BNF. Does that mean TLA+ is not a context free language? What is the relationship between the set of context free languages and the ...
1
vote
2answers
28 views

Can intersection of non-context-free languages be context-free?

For two languages over the same alphabet that are not context-free, can their intersection be context-free, Or does at least one of them have to be context-free?
2
votes
1answer
35 views

Union of non-context free languages

For two languages over the same alphabet, if neither of them is context-free, can their union still be context-free? If not, does one of the languages need to be context-free for this to happen? Do ...
2
votes
1answer
63 views

Intersection of Deterministic Context-Free Languages

If deterministic context-free languages (DCFLs) are not closed under intersection, does this mean that the intersection of two DCFLs will always be context free but may not be deterministic? Or does ...
0
votes
1answer
23 views

Context-free grammar for $ \{a^lb^n c^m |l, n, m ∈ \mathcal{N}^+, l \geq \min(n,m)\}$

I know that $L = \{a^lb^n c^m |l, n, m ∈ \mathcal{N}^+, (l ≥ n) ∨ (l ≥ m)\}$ is a context-free language, because I know the context-free grammar, i.e. $$ S \rightarrow AbZ \mid XBc \\ A \rightarrow ...

1
2 3 4 5
29