Skip to main content

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
1 answer
48 views

Possible mistake in a book regarding parsing and lexical analysis

I was just reading a book (Algorithms and Theory of Computation Handbook, Volume 1) and I came across the following passage : "From a practical point of view, for each grammar G = (Σ,V, S, P) ...
Aland Ameer's user avatar
1 vote
0 answers
47 views

Alternative solution for the Dangling Else Problem

I understand that one of the ways to solve the Dangling Else Problem is by imposing innermost binding. So, we have to transform the following ambiguous grammar: ...
Librapulpfiction's user avatar
-1 votes
0 answers
43 views

Is the language of an equal number of as bs and cs context free?

The following question appears in my textbook. Is the language, $L$, of all words over $Σ=\{a,b,c\}$ that have the same number of $a$'s $b$'s and $c$'s context free? $L = \{abc,\ cba,\ cbacab,\ ...
Jordan's user avatar
  • 1
-1 votes
0 answers
23 views

Is the language of an equal number of as and bs followed by any number of cs context free?

Consider the language $L=\{a^n b^n c^m \mid n, m \in\{1,2,3\ldots\}\}$. Note that $n$ is not necessarily equal to $m$. Prove whether or not this language is context free. I believe that it is context ...
Jordan's user avatar
  • 1
0 votes
1 answer
35 views

Should a PDA reject words not in language?

Let's say we want to construct the PDA for the following language: $$L_4 = \{w_1bw_2 | w_1, w_2 \in \{a,b,c \}^* \ and \ (\#ab\in w_1) = (2 \times \#c \in w_2)\}$$ Let's consider the following PDA ...
lezaf's user avatar
  • 111
7 votes
1 answer
320 views

Are Context-Free languages closed under XOR?

First, let's generalize the notion of XOR on strings over the ${0,1}$ alphabet. For strings of the same length, the XOR is the bitwise XOR. For strings of different lengths, we define $ \text{xor}(w, \...
Toobatf's user avatar
  • 73
5 votes
2 answers
669 views

Is the complement of this context-free language also context-free?

Question from an old exam: Consider the alphabet $A=\{a, b, c, 1, 2\}$ and two fixed words $u=aaab$ and $v=baac$. Let $\mathcal{G}$ be a context-free grammar with the rules $$ S \rightarrow \epsilon |...
Michał's user avatar
  • 165
0 votes
1 answer
30 views

Question about a grammar who generates $(0+1)^*$

On a test from my Automata theory class of last year, I have seen an excercise that gives the free context grammar $G$ with the following rules: $$S \rightarrow 0S1 | S0 | 1S | \varepsilon$$ and asks ...
Daniel García's user avatar
-1 votes
1 answer
26 views

Create a cfg for the language L = {w ∈ {a,b,c}* : |w| = 3na(w)}

All I know about this language is that it is equivalent to the following: $$L = \{w \in \{a,b,c\}^{∗} : n_b(w) + n_c(w) = 2 * n_a(w)\}$$ but I have absolutely no idea how to create a CFG for it.
AmirMohammad Shakeri's user avatar
0 votes
1 answer
25 views

Discard all ambiguity from given CFG

Here is given CFG : CODE→VDECL CODE | FDECL CODE | ϵ VDECL→vtype id semi | vtype ASSIGN semicolon ASSIGN→id assign RHS RHS→EXPR | lit | char | bool EXPR→EXPR addsub EXPR | EXPR multdiv EXPR EXPR→...
bFur4list's user avatar
  • 103
1 vote
1 answer
50 views

Rough sketch for an Algorithm to show that a context free grammar G generates only words that are solely made up of b's

The title is a bit long but bare with my english skills. As the title says I have a the task to give a rough sketch for an algorhitm that checks whether a give grammar G, with the alphabet {a,b,c}, ...
pewwwpewww's user avatar
2 votes
2 answers
46 views

Termination of standard encoding of CFG as PDA for words not in the language

The construction of a PDA from a CFG on wikipedia (1) is like a nice exercise for implementing a minimal-and-slow-but-functional parsing algorithm. I have a question about termination of the PDA that ...
bobismijnnaam's user avatar
2 votes
1 answer
56 views

Counting words in an unambiguous context-free grammar

Given an unambigious context-free grammar $G = (\Sigma, V, \mathcal R, S)$, is there a polynomial-time algorithm that calculates $|L(G)|$ (including the case where $|L(G)|$ is infinite)? The rough ...
Olly Britton's user avatar
0 votes
2 answers
50 views

Proving a Language is Not Context-Free

How to demonstrate that a specific language is not context-free using pumping lemma? Hello everyone, I'm grappling with a theoretical computer science problem and seeking advice or confirmation on my ...
Harold 's user avatar
2 votes
1 answer
35 views

How to demonstrate that the intersection of a context-free and a regular language is context-free?

I'm working on a theoretical computer science exercise and need some help with solving it. Here's the task: Task: Let $C$ be a context-free language and $R$ a regular language. Show that $C \cap R$ is ...
Harold 's user avatar
-1 votes
2 answers
108 views

Number of a, b and c is even

The language of strings over $a$, $b$ and $c$ such that the number of $a$ is even, the number of $b$ is even and the number of $c$ is even is clearly regular (it is easy to construct a FA or a RE for ...
Marcus's user avatar
  • 139
0 votes
1 answer
34 views

Which one is more restricted CNF or GNF

I think that CNF should be more restricted due to its format rather than GNF. CNF has more restricted format compared to GNF
Riya's user avatar
  • 11
1 vote
1 answer
40 views

Why we can reduce $A_{TM}$ to $ALL_{CFG}$, but we can not reduce $A_{TM}$ to $E_{CFG}$

If a $PDA$ can be constructed to check whether a string is not a computation history for a Turing Machine. Like in the proof of $ALL_{CFG}$ is not decidable. Then we can construct a $PDA$ that accepts ...
Air Homely's user avatar
0 votes
1 answer
64 views

Is the language {a^m b^n a^n b^m | m, n >= 1} context free?

Based on my understanding, I ended up at the following grammar: A -> bAa | λ S -> aSb | A | λ Is it sufficient to say the above language $L = \{a^m b^n a^n b^...
Kilaru Vasudeva's user avatar
1 vote
2 answers
43 views

Reduce the problem of CFGs with equal languages to the problem of CFGs generating a palindrome

Consider the problem of, given two CFGs $G_1$ and $G_2$, deciding whether they accept the same language, $L(G_1)=L(G_2)$. Call this problem $EQ_{CFG}$. Also consider the problem of deciding whether a ...
Addem's user avatar
  • 367
2 votes
1 answer
132 views

Efficiently transforming non-recursive CFG into an NFA

It should be possible to rewrite a non-recursive CFG [1] as an acyclic NFA, since non-recursive CFGs represent finite languages (and thus regular a fortiori). Is there an explicit algorithm to rewrite ...
breandan's user avatar
2 votes
1 answer
33 views

Decidability of whether for a given $G$, $L(G)=\Sigma^+$? (or $L(G)=L$ where $L$ is fixed beforehand

If $G$ is a CFG, is it decidable whether $L(G)=\Sigma^+=\Sigma^*\setminus\{\epsilon\}$? I have no idea which in direction to go. I feel like it is undecidable, but can't seem to find any proof. I ...
PranksterSabeleye's user avatar
7 votes
1 answer
123 views

Is it decidable if $\text{MIN}(L(G))$ and $\text{MAX}(L(G))$ is context-free for a context-free grammar $G$?

Let $L$ be a language over an alphabet $\Sigma$ and let $$ \text{MIN}(L) = \{ w \in L \mid \forall x,y \in \Sigma^* : (w = xy \land x \in L) \implies y = \varepsilon \} $$ $$ \text{MAX}(L) = \{ w \in ...
JimmyB's user avatar
  • 213
0 votes
0 answers
22 views

Is complement of this language context-free? [duplicate]

Let $L = \{wcw : w \in \{a, b\}^\ast\} \subseteq \{a, b, c\}^\ast$. From what I know, this language is not a context-free language but how about complement of this language? I know that the class of ...
Abel's user avatar
  • 1
0 votes
1 answer
36 views

Context Free Grammar: How to infer FIRST()

We are given the grammar rules $A \to F B E$ $B\to A C$ These rules are only some of the rules of a larger grammar $G$, but we are not given the remaining rules of $G$. We are told that $A$ is ...
tmhs's user avatar
  • 97
0 votes
1 answer
54 views

A context-sensite grammar for the language of sequences of two different types of parentheses with possible intersections?

Consider the language $L$ over the alphabet (,[,),] such that any word $w \in L$ if formed as a shuffle of two (possible empty) well-formed sequence of parenthesis: one over (,) and another over [,]. ...
kerzol's user avatar
  • 103
2 votes
1 answer
114 views

Is matching pairs sufficient?

Book PDF: https://vishub.org/officedocs/13770.pdf Pg 253 of book This is a snapshot from Dexter C. Kozen - Automata and Computability, Lecture-35, Undecidable problems about CFLs. My question here is ...
PranksterSabeleye's user avatar
1 vote
2 answers
71 views

Finding the Smallest Language Class containing a given language definition

Given two regular languages L1 and L2 over alphabet Σ, we define the operator RQ(L1, L2) = {w | there exists a word v in L2 such that wv is in L1}. The task is to determine the smallest language class ...
Oh No's user avatar
  • 11
-4 votes
1 answer
64 views

Creating a context-sensitive grammar (CSG) for the language L = {anbna2n: n ≥ 1}

Need a grammar that can create this language, I am having issues getting a language to work and was looking for help.
user168937's user avatar
1 vote
0 answers
54 views

A proof that $a^n b^m $ for $n\neq m$ is not regular by using the pumping lemma

I am looking at $L=\{a^nb^m |n\neq m \}$. I would like to prove that $L$ is not regular. This can easily done by assuming it is regular and looking at $\overline L$, or by using other theorems. ...
Eric_'s user avatar
  • 465
1 vote
2 answers
90 views

Subset Relations Between CFGs and Their Languages

Is it possible for there to exist two context-free grammars where the set of rules of the first is a proper subset of the set of rules of the second, yet the language generated by the second grammar ...
Mocak's user avatar
  • 15
-1 votes
1 answer
83 views

What is the regular language for L = {w | w has even length, and starts and ends with the same symbol}?

I originally thought it was 0(01)*(01)0 U 1(01)(01)1 where: two versions: one that starts and ends with 0, the other that starts and ends with 1 connected by plus, which does not mean union of both ...
cool cat's user avatar
1 vote
0 answers
36 views

Efficiently generating valid strings from a deterministic CFG, one symbol at a time, subject to a length limit

Background I'm writing algorithms for generating arbitrary strings from a formal language $L \subseteq \Sigma^*$, one symbol at a time from left to right, while also ensuring that the strings do not ...
Jerry Ding's user avatar
1 vote
1 answer
37 views

Parse tree choices for proving the pumping lemma for CFL

I was studying pumping lemma for CFL and in the proof it says that, we choose the shortest parse tree if there are multiple parse trees and we also choose $R$ the repeating variable such that it's the ...
hxdshell's user avatar
1 vote
1 answer
78 views

A problem maybe related to pattern-matching

Let $\Sigma_{1}=\{a,b\}$ and $\Sigma_{2}=\{t,f\}$. Define the function $f_{w}:\Sigma_{1}^{*}\rightarrow\Sigma_{2}^{*}$ for every $w\in\Sigma_{1}^{*}$; $f_{w}(w')\in\Sigma_{2}^{*}$ is the word obtained ...
Tigerion's user avatar
0 votes
0 answers
18 views

General rules to tell if a language is regular/CFL/decidable/recognizable

I've been looking online for quite some time for some 'general' rules on this. for example, there's a 'rule' that claims that if a language is like $$L={w\in {a,b,c}^* : count_\alpha (w) =count_\beta (...
Aishgadol's user avatar
  • 355
0 votes
0 answers
45 views

PDA equivalent to an $\varepsilon$-free PDA

Say that a PDA is $\varepsilon$-free if it contains no $\varepsilon$ transitions (that is to say, $\varepsilon$ is not in the recognized string symbols even if it still is a stack symbol), but it may ...
Addem's user avatar
  • 367
0 votes
0 answers
20 views

The language made from the context free Language (CFL) is also a CFL? [duplicate]

Let $\Sigma$ be the set {a,b} of letters. For a language $L\subset\Sigma^{*}$ over $\Sigma$, we define $\Gamma(L)$ as follows; $\Gamma(L)=\{v\in\Sigma^{*}|\exists w\in \Sigma^{*}.(|v|=|w|\wedge vw\in ...
Tigerion's user avatar
0 votes
1 answer
73 views

Deciding if a language is CFL or in $P$

I'm trying to decide whether $L_c=${$w=uxu, | \ u,x\in \Sigma ^* \ and \ |u|=c $} for some constant $c\in \mathbb{N}$ is context free or not. initialliy, I've thought about choosing $x=\epsilon$ ...
Aishgadol's user avatar
  • 355
-1 votes
2 answers
101 views

Is $L=\{a^nb^m : n\neq 7m, \ n,m\in \mathbb{N}\}$ context free?

I'm asked to categorize the language $L=${$a^nb^m : n\neq 7m, \ n,m\in \mathbb{N}$}, therefor I need to distinguish if it's regular, context free, or non context free (in $P$) We know CFLs are closed ...
Aishgadol's user avatar
  • 355
-1 votes
2 answers
62 views

Context free grammar for $L=\{a^nb^m : 2m<n<4m\}$

The thing that confuses me here is that i've seen a similar example where $L=\{a^nb^m : 2m\leq n\leq 4m\}$ where the CFG was straight forward: $$ S\rightarrow aSbb\\ S\rightarrow aSbbb\\S\rightarrow ...
Aishgadol's user avatar
  • 355
2 votes
1 answer
707 views

Is there a one-state PDA that recognizes every context free language?

Here, I read this: For all CFL, there is a one-state PDA that recognizes this language. What is the proof/idea behind this claim? CFL: Context Free Languages PDA: Push Down Automaton
whoisit's user avatar
  • 165
1 vote
3 answers
456 views

Proving that L = {x ∈ {a, b}∗ | na(x) < nb(x) < 2na(x)} is not a context free language

I've been working on proving that this language L = {x ∈ {a, b}∗ | na(x) < nb(x) < 2na(x)} is not Context Free. "na(x)" stands for "number of ...
Librapulpfiction's user avatar
1 vote
2 answers
90 views

How to construct context-free language $L$ to prove $L′=\{x|xx∈L\}$ is not context-free?

Can someone please explain me how to solve this? In this post here was one user sketching the solution but I still don't understand how to construct a context-free language $L$ in such a way that the ...
shinichi's user avatar
0 votes
1 answer
96 views

How to put the given context-free grammar into Chomsky Normal Form?

I have questions about how to put the grammar below in CNF - Chomsky Normal Form: S ->aAa | bBb | ВВ; A -> C; B -> S | A; C -> S | ε; I did it like this: I eliminated empty productions: ...
Crow G. F.'s user avatar
3 votes
1 answer
65 views

Is there a linear language $L$ such that $\overline{L} \in \texttt{Type-2} \setminus \texttt{Lin}$?

This question is kind of a follow-up to a question asked a few days ago. Both of the non-linear complements of linear languages found were also not context free. So the question is this: Is there some ...
Knogger's user avatar
  • 1,372
0 votes
0 answers
62 views

Can Shared Packed Parse Forest have more than 2 families?

I am implementing Earley parser and using algorithm from Elizabeth Scott's paper "SPPF-Style Parsing From Earley Recognisers" (section 4). Author says A family of children of u will consist ...
Somnium's user avatar
  • 275
1 vote
1 answer
46 views

Accept $L=\{ww^r:w\in\Sigma^*\}$ in less that $|w|$ storage

Suppose $L=\{ww^r:w\in\Sigma^*\}$. Already, we know that we can draw a PDA for $L$ such that accept each $w\in L$ with space complexity at least $|w|$. My question is how is it possible to draw a PDA ...
ErroR's user avatar
  • 1,942
0 votes
1 answer
63 views

How it possible given string belong to given grammar

Consider this context-free grammar: $$G:\\\;\; S\to aSbb|aaSbbb|\lambda$$ Is the string $a^{2020} b^{4020}\in L(G)$? I try to derive such a string but I can't, how it possible?
ErroR's user avatar
  • 1,942
2 votes
1 answer
150 views

The complement of a particular language

We know that Linear context-free languages are not closed under complement, so I encountered a challenge in finding an example to show the above theorem. I think the complement of $L={a^nb^n}$ is not ...
ErroR's user avatar
  • 1,942

1
2 3 4 5
35