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
2
votes
2answers
71 views

Writing a grammar for lambda calculus

I'm trying to write a context-free grammar (to be feeded to lark) for parsing lambda calculus expressions. Basic version of it, as presented by most sources, looks like: ...
3
votes
1answer
56 views

Is $\{ w_1cw_2 \mid w_1 ≠ w_2 \}$ a context-free language?

Is the language $L_1 = \{w_1cw_2 ~|~ w_1,w_2 \in \{a,b\}^{\ast} \text{ and } w_1 \neq w_2\}$ a context-free language? It certainly isn't regular, but is it context free? I'm having trouble creating ...
3
votes
1answer
68 views

Language whose intersection with a CFL is always a CFL (2)

This is a follow-up to this question, which asks for an example of a non-regular language $L$ which satisfies the following condition, intersection resilience: If $L'$ is context-free then so is $L ...
1
vote
1answer
27 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 ...
0
votes
0answers
48 views

What does pump down means in this solution?

Problem text (from Sipser's "Introduction to the Theory of Computation"): 2.42 Let $E = \{1,\#\}$ and $Y = \{ w \mid w = t_1\#t_2\# ...... \#t_k \, \text{for $k \geq 0$, each $t_i \in 1^*$, and $...
1
vote
1answer
50 views

context-free grammar for comma-separated list with comments

I'm trying to write a context-free grammar for a comma-separated list of statements with comments. It is trivial if the comma appears at the end of a statement. It is trivial if the comment is ...
3
votes
0answers
44 views

Conditions that imply closure under intersection of context-free languages

Context-free languages are not closed under intersection. Suppose $L_1, L_2 \in CF \setminus REG$ (i.e., $L_1,L_2$ are context-free but not regular). Are there well-known theorems (and/or whole ...
2
votes
1answer
65 views

In what sense a type of parser is less power than the other?

I am learning LR(0), SLR(1), CLR(1) and LALR(1) parsers. I know how parsing tables of each of them is formed. If x < y means parser x is less "powerful" that parser y, then, I read, the ...
5
votes
1answer
244 views

How to prove the emptiness of intersection of two context free languages is undecidable?

Where can I find a proof that the emptiness problem for the intersection of two context free languages is undecidable? I searched on the internet but could not find anything helpful. Do you maybe ...
1
vote
1answer
31 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
37 views

Find PDA for CFL = {x#y | |x| = |y| and x ≠ y} [duplicate]

I am studying push down automata. When I read a solution for showing $L = \{x\#y \mid x \neq y, x,y \in \{0,1\}^*\}$ is a CFL, I could understand $L = L_1 \cup L_2$, $L_1 = \{x\#y\mid|x| \neq |y|\}$, ...
1
vote
1answer
47 views

Creating a CFG from a specific CFL

I am pretty desperate finding the correct context free grammar for the following language: $$L=\{a^lb^mc^n \mid l,m,n \in \mathbb{N}_0, \, l\geq 2n+m\}$$ I would really appreciate if anyone could ...
0
votes
0answers
16 views

About Specification of PDA

I was learned NPDA is specified by a tuple $P = (Q,\Sigma,\Gamma,\delta,q_0,Z_0,F) $, $Q$ is a finite set of states $\Sigma$ is a finite set of input symbols (input alphabet) $\Gamma$ is a finite ...
1
vote
1answer
48 views

Proving that the set of grammars generating L or L complement is undecidable

Let $X$ be a regular language, I need to prove that either $\{G \mid L(G) = X\}$ or $\{G \mid L(G) = \overline{X} \}$ is undecidable using the following hint: Use reduction to absurdity supposing that ...
1
vote
1answer
33 views

Undecidability of checking whether all words can be generated from a context-free grammar?

I know it's undecidable, but how to prove it? Let me explain the problem clearer. The problem is not to check whether some given word can be generated, but whether ALL words are possible to generate ...
3
votes
1answer
50 views

Is there an algorithm to overapproximate a context free grammar by a regular expression?

I understand that a context-free grammar is strictly powerful than a regular expression in that a context free grammar can represent any regular language, but not all context free languages can be ...
0
votes
2answers
127 views

Convert this language to Context Free Grammar

I'm having trouble understanding how to convert this language to context free grammar. $\{a^ib^jc^k\mid i > k, 0\le j \lt3, k \ge 0\}$ Part im getting stuck on is how to deal with a and c, ...
-1
votes
2answers
138 views

CFG for L {a^nb^m | n <= m+3}

I need a Context Free Grammar for this language. I could come up with this solution: S -> AB A -> aA | ε B -> bbbB | ε But, this grammar is clearly ...
0
votes
2answers
115 views

CFG for the language L ={a^n w | w \in {b,c}^*, n= count of b.c in w. }

$L =\{a^nw \mid w \in \{b,c\}^*$, $n=$ #$_b$ + #$_c$$\}$ $\bullet $ #$_b$ denotes the number of $b$'s in $w$ $\bullet $ #$_c$ denotes the number of $c$'s in $w$ I have some trouble designing a CFG ...
-1
votes
1answer
126 views

Constructing PDA to accept language { 0^i 1^j 2^k | i = 2j or i = k, where i,j,k >= 1 }

$L = \{ 0^i 1^j 2^k \mid i = 2j \text{ or } i = k, \text{ where } i,j,k \geq 1 \}$ I have trouble about this PDA. Anybody can help me about draw this PDA?
0
votes
0answers
32 views

Is there any grammar parseable by LALR(1) but not LR(1)?

https://en.wikipedia.org/wiki/LALR_parser - as far as I understand, LALR(1) is a simplified version of LR(1), aiming to achieve a greater parsing performance at the expense of reduced power. So, IIUC, ...
0
votes
1answer
46 views

What are the sufficient conditions for a grammar to be unambiguous?

There is no algorithm that, given an arbitrary grammar, decides if it's ambiguous or not. However, Are there any sufficient conditions that make it easier to tell that a grammar is unambiguous? For ...
2
votes
2answers
61 views

Operator name in LL(1) computation

I'm working from a definition of the LL(1) property of context-free languages in order to build a LL(1)-computer, i.e., a program capable of determining whether a given context-free language is in LL(...
0
votes
0answers
174 views

a^nb^nc^nd^n using 2-stack PDA

I need to construct a PDA using 2 stacks for accepting the language $L = \{a^nb^nc^nd^n | $ $n \geq 0\}$. Pushing $a$'s to first stack and $b$'s to second and poping them for corresponding $c$'s and ...
2
votes
2answers
38 views

Why can we (apparently) implement CFG parsers only using (N)DFAs?

I am working on a project in which I need to parse files written in different DSLs. One important feature of these languages is that most of them allow blocks to be nested. For parsing those files I ...
1
vote
1answer
233 views

Binary strings such that the sum of 0's is not equal to twice the sum of 1's

Construct a context-free language for $L=\{w\in \{0,1\}^* \mid n_0(w)\not= 2n_1(w)\}$. Here $n_b(w)$ is the number of $b$'s in $w$. I can construct a CFL in the case $n_0(w)=2n_1(w)$, but I have no ...
2
votes
1answer
51 views

Finding an unambiguous grammar of a language provided by a CFG

I'm working through 'Intro to Automata Theory, Language and Computation' 2nd edition by Hopcroft, Motwani & Ullman. In section 5.4, exercise 5.4.3 I am tasked with finding an unambiguous grammar ...
1
vote
2answers
100 views

How do I model line comments in a CFG?

Assume we want to define a context free grammar of say a programming language, where on each line everything after the character # until the end of line is considered a comment and should be ignored. ...
1
vote
0answers
85 views

Accounting for spaces in grammars

Sometimes in a context free language we'd like to require spaces between productions, and sometimes not. For example take the following part from a grammar describing grammars: ...
1
vote
1answer
50 views

Can the complement of a context-free language be regular?

I know that the context-free language is not closed under the complement , and the result could be context-free language or non-context free language but my question is : is it possible of the ...
2
votes
1answer
31 views

Equivalent unambiguous grammar

Given the grammar: $S \to AS\mid \varepsilon$ $A \to A1\mid 0A1 \mid \varepsilon$ Generate a new unambiguous grammar that generates the same language as the grammar above. I have no idea how to ...
1
vote
2answers
33 views

Proving that a specific grammar is ambiguous

How can I prove that the following grammar is ambiguous: $$ A \to AA\mid B \\ B \to aBb\mid ab $$ I tried finding a string that can be derived in two different ways, but to no avail.
0
votes
1answer
40 views

Crafting a Context Free Grammar

I'm trying to figure out the intuition on creating a CFG in my head. I understand the idea of Grammar rules akin to "onions" with various layers throughout. For example, I was working on a problem ...
2
votes
3answers
53 views

When are two CFG's different?

If two CFG's differ only in what names they use for their non-terminals, are they different? For example, are these CFG's different: $$\begin{align*} S &\to A \\ A &\to a \end{align*}$$ and $...
2
votes
1answer
69 views

The language $\{ww \mid w \in \{0,1\}^{*} \}$ is not a CFL

We have proved that the language $ L = \{\omega\omega \mid \omega \in \{0,1\}^{*} \} $ is not a CFL, and we did so by using pumping lemma. And the proof is clear to me. But I thought of the following ...
1
vote
1answer
313 views

Language whose intersection with a CFL is always a CFL

Prove or disprove: If the language $L$ is such that for every context-free language $L_0$, the language $L \cap L_0$ is context-free, then $L$ is regular. I haven't managed to prove this, but I'm ...
0
votes
1answer
52 views

Finding a mapping reduction from $A_{TM}$ to $\overline{CF_{TM}}$

I am trying to find a mapping reduction from $A_{TM}$ to $\overline{CF_{TM}}$, but I can't seem to find one. Definitions: $$\begin{align*} CF_{TM} &= \left\{ \langle M \rangle \mid \text{$M$ is a ...
-3
votes
1answer
64 views

Context Sensitive Grammar for the language $\{a^n b^n c^{2+k}\mid n \ge 1, 0 \le k\le 1\}$ [closed]

I'm studying for my final exam and come up with this exercise with no idea how to find the production rule of this grammar. I need help. Thanks all of you! :)
1
vote
1answer
35 views

Is substitution done to all occurrences?

In a CFG, we might have :$A \rightarrow AA$ and $A \rightarrow a$ where $a$ is a terminal and $A$ is a variable. Then if we apply the first rule, and then the second , do we get $aa$ or either $aA$ ...
2
votes
3answers
88 views

Are $CF_{TM}$, $\space $ $\overline{CF_{TM}}$ Turing-recognizable?

I have searched the site well through, and also using Google and notes and couldn't find an answer to a question I am wondering about. Given: $$CF_{TM} =\{ \langle M \rangle \mid \text{$M$ is a TM ...
2
votes
0answers
31 views

Generating context-free grammar from language [duplicate]

I need to give a context-free grammar for each of the examples: $L_1=\{a^hb^ka^mb^n : h+k=m+n\}$ $L_2=\{a^ib^ja^k : (i=j \,\,\,\, and \,\,\,\, k≥0) \,\,\,\, or \,\,\,\, (i\ge0 \,\,\,\, and \,\,\...
0
votes
0answers
28 views

How to make the length even for the words whose number of 0s is double its number of 1s? [duplicate]

How do I make a context-free grammar (CFG) for the following language? $$L = \{w \in \{0, 1\}^* : \#_0(w) = 2\#_1(w)\text{ and } |w|\text{ is even}\}.$$ I have $$S \to S1S0S0S \mid S0S1S0S \mid ...
1
vote
1answer
150 views

For any two regular languages A, B, show that {xy|x ∈ A, y ∈ B, |x| = |y|} is context-free

Basically I'm wondering if the concatenation of two equal length string is context free. I've seen multiple proofs of this online using PDAs but we aren't covering them in my automata course and my ...
5
votes
1answer
141 views

Is a kind of reverse Kleene star of a context-free language context-free?

Recently I had a question on one of my assignments asking to prove or disprove the following: Let $L$ be a language. If $L^*$ is context-free then $L$ is context-free. Now obviously this is false ...
1
vote
1answer
82 views

Proving that L(G) is the language defined by the CFG G

I have a context-free grammar defined by the production S: S → aSbS ∣ bSaS ∣ ε I need to prove that the CFG "G" can be defined as a language L(G) where L(G) = {w ∈ {a, b}∗ ∶ na(w) = nb(w)}. ...
1
vote
0answers
49 views

How to generate random strings from Context-Free Grammar in GNF

I need to generate random strings given a grammar in Greibach Normal Form. The naive approach would be to generate a random integer n and perform ...
0
votes
1answer
46 views

Context free grammar for L={ ((ab)^n)^m }

I want to write a cfg for the following language: $ L = {((ab)^n)^m }$ $m,n >= 0$ this language produces (abababababab) where: $n=2, m=3 \\ or \\ n=3, m=2$ I have no idea what to do with it!
10
votes
2answers
735 views

Language involving irrational number is not a CFL

I am working through a hard exercise in a textbook, and I just can't figure out how to proceed. Here is the problem. Suppose we have the language $L = \{a^ib^j: i \leq j \gamma, i\geq 0, j\geq 1\}$ ...
0
votes
0answers
54 views

Proving the Complement of a DCFL is DCFL [duplicate]

If I Have a DCFL $L$ ( a CFL which can be recognised by a DPDA ), How do I prove that $\overline{L}$ is also a DCFL I checked my textbook for a proof but I wasn't able to understand the language. Can ...
0
votes
0answers
38 views

construct regular expression for a language [duplicate]

I want a regular expression for the following language. (a+b+c)*, but does not contain substring "abab". That means it can be any combination of (a, b, c) except "abab". I tryed to construct it ...