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
34 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
44 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
0 answers
18 views

What is the grammer of L = {a^m b^n a^p : 2n = m + p} [duplicate]

what's the grammar of the following Language : L = {a^m b^n a^p : 2n = m + p}
new c learner's user avatar
2 votes
1 answer
101 views

Is matching pairs sufficient?

This is a snapshot from Dexter C. Kozen - Automata and Computability, Lecture-35, Undecidable problems about CFLs. My question here is that, why should we check triples (3-element substrings)? Why not ...
PranksterSabeleye's user avatar
-4 votes
0 answers
76 views

Construct a PDA that recognizes { w | w in {0, 1}* where w = xy, with |y| ≤ |x| ≤ 3|y|, and x contains at least four 1s }. My PDA has 11 states

This question has been a total nightmare. I have no idea how to make this and any help would be appreciated.
keth's user avatar
  • 1
-5 votes
0 answers
15 views

Which of the next sets is the set of right recursive nonterminals?

These are rules: $S \to a B A \mid B X A$ $B \to X A A X \mid a b C$ $X \to aa X \mid ε$ $A \to A S b X \mid ε$ $C \to X A B X \mid ab X A$ $Y \to a B A X B \mid ab X A$ $N = \{S, A, B, C, X, Y \}$, ...
Dmytro Kurdomanenko's user avatar
1 vote
2 answers
62 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
0 answers
16 views

Comp theory course [duplicate]

I have this language , le langage L={ a ^ s * b ^ t * c ^ m / where s >= t or s >= m } I cant find a grammar for this language please help me Grammar like S -> aS……
katia akkou's user avatar
-3 votes
1 answer
37 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
43 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
  • 445
1 vote
3 answers
81 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
36 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
30 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
33 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
15 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
43 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
  • 335
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
99 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
61 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
659 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
388 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
74 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
66 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
58 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,032
0 votes
0 answers
58 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
44 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,910
0 votes
1 answer
61 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,910
2 votes
1 answer
139 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,910
3 votes
1 answer
313 views

Repeated rules with more than three symbols for conversion to Chomskys Normal Form

I am trying to convert the below context-free grammar into Chomsky Normal Form, specifically, removing rules that have three or more variables or terminators. $$S \to A a B \;\vert\; B b C$$ $$A \to A ...
pleaseandthankyou's user avatar
2 votes
1 answer
40 views

What does the language of DFA of LR itemsets represent?

As we know, if we want to make a $LR(0)$ (say) parsing table for a context free grammar (CFG), we prepare the $LR(0)$ itemsets with $.$ (dot) in RHS of the CFG production. With this $.$ we keep track ...
Ajit Kumar's user avatar
-1 votes
1 answer
41 views

Is this correct Context free grammar(CFG) for these two languages?

Question 1: L = { 0^n 1^n | n > 0 } My answer = S -> 0 S 1 | 10 Question 2: L = { 101^n0^2n | n > 0 } My answer = S -> 101 S 00 | 100 Can anyone correct this if there is any issue with ...
Elijah's user avatar
  • 1
0 votes
0 answers
29 views

Why in the pumping lemma of a context free grammar $|vy| > 0$ and $|vxy| ≤ p$?

Let us consider the case where $p > 0$ exists and a string $|w| ≥ p$ can be divided into $uv^{i}xy^{i}z$ for each $i ≥ 0$. When we say that $|vy| > 0$ do we mean that at least one of the two ...
Luca 's user avatar
  • 63
2 votes
1 answer
59 views

Is the language accepted by a DFA with a fixed word on the stack after consuming it a deterministic context free language?

Let $\cal M$ be a deterministic stack automaton ${\cal M } = (Q, \Sigma, \Gamma, \delta, q_0, F, Z_0 )$. Let $\gamma \in \Gamma^* $ a word on the stack alphabet. Is it true that the language $$L = \{ ...
hedphelym's user avatar
  • 125
2 votes
2 answers
80 views

Does the pumping lemma for context-free languages really require accepting a string with zero levels of nesting?

In the pumping lemma conditions for context-free grammar we have that the string can be divided into $uv^{i}xy^{i}z$, but in the case of $i = 0$, why does it still belong to the language?, is it ...
Luca 's user avatar
  • 63
0 votes
0 answers
33 views

It shows that CF grammar is ambiguous

Let $G$ be the CF grammar that has the production rules: $S \to aS | aSbS | c$. Show that $G$ is ambiguous. I thought of proving it by representing the string $aacbc$ but I don't know if it is correct ...
Luca 's user avatar
  • 63
1 vote
1 answer
62 views

How to prove that $L = \{{a^{n} b^{n} c^{j} | n,j \geq 0}\}$ is a CFL?

In the text of my book it says that this language is context-free so I tried to prove that the conditions of the Pumping Lemma are fulfilled. If, for example, I take the word $aaabbbc$ I can divide it ...
Luca 's user avatar
  • 63
1 vote
1 answer
83 views

what's the time complexity of finding all nullable symbols in context free grammar?

I'm reading Hopcroft's book about computation theory and wondering about how fast can u find all nullable symbols in CFG.
khajaba khangal's user avatar
1 vote
1 answer
52 views

CFG {$w\in ${a,b,c}$^* | $#$_a(w) + $#$_b(w) = $#$_c(w)$}

I'm practicing the following exercise for my exam: CFG {$w\in ${a,b,c}$^* | $#$_a(w) + $#$_b(w) = $#$_c(w)$} and I'm struggling a bit. I've already solved {$a^nb^mc^l | n+m=l$} with production rules: $...
Jellyfish's user avatar
2 votes
2 answers
140 views

Are there context-free languages whose both intersection and complement of intersection are non-context-free?

It is well known that context-free languages are not closed under intersection or complement. But what about context-free languages $L_1$ and $L_2$, such that $L_1 \cap L_2$ as well as $\left( L_1 \...
Buco's user avatar
  • 21
0 votes
1 answer
157 views

Context free grammar $\{0^n 1^m : n,m \geq 0\}$

I just started studying the concept of context-free grammars and I find something very confusing. Watching a video I found someone tackling the problem ${0^n 1^m : n,m\geq 0}$. I thought that the ...
Jellyfish's user avatar
0 votes
0 answers
22 views

CFG PL for L=\{a^ib^j \mid j = i^2\}

where i got it from. This was weird so I wanted to try it myself because they way he did it seemed wrong. So this is my attempt is it correct? I did not add the basic parts of the pumping lemma proof ...
Grandma Kisses's user avatar
0 votes
1 answer
30 views

What is the name of the diagram used in JSON spec for representing a context-free language?

If you go to the JSON spec page : https://www.json.org/json-en.html, then you'll see the language represented by some diagrams showing graphically what the language looks like. I wondered, does this ...
hl037_'s user avatar
  • 103
0 votes
0 answers
49 views

Two Counter word count language Nondeterministic Pushdown Automata (NPDA) problem actually Context Sensitive unless counters are multiples

Classic text (Linz, P., & Rodger, S. H. (2022). An introduction to formal languages and automata. Jones & Bartlett Learning.) describes the following language where one is to describe an ...
John Daniels's user avatar
0 votes
0 answers
3 views

Two Counter word count language npda' problem actually Context Sensitive unless counters are multiples [duplicate]

Classic text (Linz, P., & Rodger, S. H. (2022). An introduction to formal languages and automata. Jones & Bartlett Learning.) describes the following language where one is to describe an ...
John Daniels's user avatar
0 votes
0 answers
4 views

Two Counter word count language npda' problem actually Context Sensitive unless counters are multiples [duplicate]

Classic text (Linz, P., & Rodger, S. H. (2022). An introduction to formal languages and automata. Jones & Bartlett Learning.) describes the following language where one is to describe an ...
John Daniels's user avatar
1 vote
2 answers
389 views

Does there exist an context free language L such that L∩L^R is not context free?

By the closure property of context-free languages, if $L$ is context-free, then $L^R$ (the reverse of $L$) is also context-free, but $L\cap L^R$ might be non-context-free. I tried to come up with an ...
Miki's user avatar
  • 11
2 votes
2 answers
90 views

Derivation trees to show a given grammar is ambiguous

Given the grammar with productions: \begin{align} S \rightarrow aSb \mid SS \mid \lambda\\ \end{align} I would like to show that it is ambiguous. As I understand it, if you can show that some string ...
cpf9231's user avatar
  • 21
0 votes
1 answer
57 views

Proof that $\{0^m 1^n : 0\le m\le n^2\}$ is not a CFL

I am trying to prove by the pumping lemma that $L=\{0^m1^n:0\le m\le n^2\}$ is not a CFL. Here is what I have so far. Suppose for contradiction that it is a CFL and let $N$ be the pumping length. ...
Addem's user avatar
  • 335

1
2 3 4 5
35