Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more

Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

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

is there a way to eliminate indirect left recursion of this grammar?

I have an indirect left recursive grammar: expr_1 := expr_1 ... ...
peterparker's user avatar
0 votes
1 answer
19 views

can left recursion be solved by adjusting the parser not the grammar?

Lets say I have a grammar I know that E -> E + T | T can be solved like this: E -> T ( + T)*. But instead can I just ...
peterparker's user avatar
0 votes
0 answers
35 views

transforming a grammar from EBNF to LL(2)

I have a grammar in EBNF and want to transform it into an LL(2) grammar. Should I omit A -> empty string ? And is there a scheme I can follow? So far I would ...
peterparker's user avatar
0 votes
0 answers
18 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
47 views

can programming language be described by ambiguous grammar, if yes, will that cause any problem?

When someone tries to formally describe the syntax of programming languages, they describe with context-free grammar, then for every program we can derive parse tree that would correspond to that ...
math boy's user avatar
  • 359
0 votes
0 answers
47 views

Eliminating left recursive nonterminals without adding $\epsilon$-productions

I have been reading the book "Compiler Construction" written by William M. Waite and Gerhard Goos. I found a statement in the chapter "5.3.2. Top-Down Analysis and LL(k) Grammars" ...
user42768's user avatar
  • 111
0 votes
1 answer
48 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
1 vote
0 answers
77 views

An approach to discover parameterised patterns in arbitrary strings

Expanding on Question 79182 I am sure there must be an active area of research for deriving parameterised patterns. What I am looking for is something like - given the input ...
Konchog's user avatar
  • 23
15 votes
2 answers
4k views

How do C compilers distinguish casting from grouping?

In the C language, there's the 2 similar-in-form but distict-in-meaning constructs: (type)value which is a casting, and (value), ...
DannyNiu's user avatar
  • 352
0 votes
1 answer
37 views

How are PCFGs used in programming language design?

I've been reading the wikipedia article about probabilistic context-free grammars (PCFGs), and they state that PCFGs have application in areas as diverse as natural language processing to the study ...
Knogger's user avatar
  • 1,072
0 votes
3 answers
71 views

What is the name of the theory that says that Turing equivalence is universal, and Turing machines are maximally computationally powerful?

In the Chomsky hierarchy, level 0 grammars include all languages that can be recognized by a Turing machine. There is no level -1 (which would represent the class of languages that cannot be ...
Luke Hutchison's user avatar
0 votes
2 answers
46 views

Reference types

Is a reference type (agnostic of PL) the object being pointed at, or the object doing the pointing? I'm having a hard time wrapping my head around the concept fundamentally (of course, I have ...
user129393192's user avatar
-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
4 votes
0 answers
121 views

Constructing worst case for L* by D.Angluin

I'm working on constructing deterministic finite automata (DFAs) with a specific learning complexity when using the L* algorithm developed by Dana Angluin. My goal is to create a DFA of size ( n ) ...
Coping Forever's user avatar
1 vote
2 answers
76 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
35 views

Trouble proving this is regular

I'm taking an automata class and one of the examples is showing this is regular. My initial thought was to make a DFA to show it is but i'm a bit confused on what a DFA with a standard 5 tuple would ...
user167205's user avatar
3 votes
1 answer
60 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,072
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
3 votes
1 answer
315 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
0 votes
0 answers
15 views

Finding program that enumerates a language using Von Neumman's computability paradigm

Given an alphabet $\Sigma$ of $n$ elements, whenever there is some order $\leq$ over the elements of $\Sigma$, we define $s^{\leq} : \Sigma^{*} \mapsto \Sigma^{*}$ as \begin{align*} s^{\leq} \left(...
lafinur's user avatar
  • 195
1 vote
0 answers
24 views

Mapping a grammar to a graph - Relation of Terminal Symbol and Node Coverage in Software Testing

I am currently trying map a grammar to a graph in the context of syntax- and graph-based testing. However, until now I haven't had an enlightenment how would I map non-terminals and terminals to nodes ...
Daraan's user avatar
  • 111
1 vote
1 answer
57 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
0 votes
1 answer
207 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
1 vote
1 answer
48 views

Communication complexity of Dyck language

I've been reading papers on streaming algorithms and ran across the following question which I haven't been able to answer: Consider the Dyck language $Dyck(2)$ over the alphabet $A = \{(,),[,]\}$ and ...
asamsa's user avatar
  • 11
1 vote
0 answers
20 views

Number of DCFG parse tree nodes with respect to input length

I read the question and answer at Number of nodes of a parse tree when the Grammar is in CNF?, and I'm curious about a related matter: obviously with a unrestrained LR grammar (as opposed to CNF) the ...
Petr Skocik's user avatar
2 votes
2 answers
124 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
0 answers
27 views

Lambda Calculus with State

I want to define a typed domain-specific lambda calculus which can simulate the sequence execution like common programming language. I wonder how to give its corresponding BNF, can I use ...
Ziyu Mao's user avatar
1 vote
1 answer
53 views

Is the class of star-free languages just the complement to counter languages within the regular language class?

So I'm kind of confused as I'm not that deep into the algebraic theory of languages. The wikipedia article states: Another way to state Schützenberger's theorem is that star-free languages and ...
Crea Teeth's user avatar
1 vote
0 answers
20 views

Parsing expression grammar for a language consisting of sentences with one character added or removed anywhere

Given a parsing expression grammar for a language, is there a way to make a parsing expression grammar for a new language that consists of the valid strings from the original language, plus the ...
Alex Flint's user avatar
5 votes
1 answer
440 views

Why is Dyck-2 so important for the Chomsky-Schützenberger theorem?

I have read a lot of times, that models that can parse Dyck-2 are of great importance. It appears that Dyck-2 is interchangeably used like Dyck-N. Afaik the Chomsky-Schützenberger representation ...
Crea Teeth's user avatar
0 votes
1 answer
34 views

An elementary question about grammar

Recently, I am studying grammar in automata. And, I have few information about this subject. I have a grammar with rules $\{S\to ASA, A\to aA, A\to \epsilon\}$. Is it true if I say that $S\to aASA$ ...
user163802's user avatar
0 votes
1 answer
89 views

Let P be the language of palindromes over the alphabet Σ = {0, 1}. and let P‘ be the subset of the palindromes with different numbers of 0s and 1s

Let P be the language of palindromes over the alphabet Σ = {0, 1}. and let P‘ be the subset of the palindromes with different numbers of 0s and 1s. Is P' context-free? I know that for the language of ...
empty-search's user avatar
1 vote
0 answers
82 views

How need help to specify a grammar for arithmetic expressions

I am trying to come up with a grammar for arithmetic expressions with the following order of operations: Parentheses Factorials Exponents Functions / unary plus and minus Juxtaposition (implied ...
Chris_F's user avatar
  • 111
1 vote
1 answer
87 views

Is $L=\{1^n2^n3^m : n\neq m\}$ context free?

Is the language $L=\{1^n2^n3^m : n\neq m\}$ context free? I checked and it satisfies the pumping lemma (Right?). Does it also satisfy Ogden's lemma, or any other test for being non-context free?
oleshkowitz's user avatar
0 votes
1 answer
69 views

How is $\{a^m b^n c^p d^q \mid m*n=p+q\}$ context sensitive?

I have been trying to understand how the language $L = \{a^m b^n c^p d^q \mid m*n=p+q\}$) is context-sensitive? I first encountered this question here. Would be grateful if you could provide some ...
yash's user avatar
  • 1
1 vote
1 answer
99 views

Language of equal numbers of as, bs, cs in any order not context-sensitive?

In his book "Foundations of Computing", professor Allison shows an example of "language of equal numbers of as, bs, and cs, but in any order", formally: $L = \{ w \in \{a,b,c\}^*\ |...
Barney's user avatar
  • 155
-1 votes
1 answer
87 views

Is { a^nb^na^n} a context-sensitive language?

The language $L_1 = \{ a^nb^nc^n \}$ is often given as an example of a context-sensitive language. I am wondering if the language $L_2 = \{ a^nb^na^n \}$ belongs also to the same category?
Barney's user avatar
  • 155
1 vote
0 answers
85 views

Correct way to show example of ambiguous grammar

Facing confusion due to two different texts stating different ways to show examples of ambiguous grammar, though the example exists in the first book. The second book gives a different example, as ...
jiten's user avatar
  • 187
1 vote
1 answer
79 views

The language of chains with twice as many $a$s as $b$s is regular?

I am trying to understand the pumping lemma and its instrumentation to show a certain language is not regular. My first attempt was the following problem: Let $L$ be the language of all words that ...
lafinur's user avatar
  • 195
1 vote
0 answers
33 views

What is a formal grammar equivalent to one-way stack automaton?

As the title says, is there a formal grammar characterization of the class of one-way stack languages?
Hana's user avatar
  • 11
0 votes
0 answers
38 views

Nonterminal Complexity of a context-free grammar

Suppose $G$ is a CFG. $G = (N, T, P, S)$, $Var(G)$ as the cardinality of $N$ $Var(L) $= min {$Var(G)$ | G is a context-free grammar and $L(G) = L$}. I have a problem in understanding a part of proof ...
emma's user avatar
  • 1
0 votes
1 answer
49 views

Doubt in pumping lema for context-free language

I have a doubt related to pumping lemma in CFL for which I dont find an answer, so I think is very easy because no one wonder about. The lemma says: My doubt is: Is there any restriction related to ...
user69507's user avatar
0 votes
0 answers
22 views

Decide if complement of context-free language is also a context-free language

Consider the following grammar $G$: $$S \rightarrow SA \ | \ AS \ | \ aXb \ | \ bXa, \ \ \ X \rightarrow \# \ | \ BXB, \ \ \ A \rightarrow a \ | \ b \ | \ \#, \ \ \ B \rightarrow a \ | \ b$$ Decide if ...
Stanley's user avatar
  • 13
3 votes
1 answer
2k views

Is a machine Turing-complete when it can decide a context-sensitive language?

If a machine can decide a context-sensitive language (like the language of palindromes with a non-linear center) is that fact a proof that the machine is Turing-complete? Can this be used to prove ...
Barney's user avatar
  • 155
0 votes
1 answer
210 views

Is this grammar LL(1) and what is it's parsing table?

Let G be a grammar with non-terminal A, terminal a and these productions: A -> A a It is ...
Ian Rehwinkel's user avatar
0 votes
1 answer
41 views

Find Grammar for L(G) ={a^i b^j c^k | k = i*j ;i, j ≥ 1}

Find a Grammar G, so that L(G) = {a^i b^j c^k | k = i*j ;i, j ≥ 1} Hello, I have difficulties solving this. I had a similar exercise, where the k was i+j, which was easier, because the solution was to ...
tafelwasser123's user avatar
0 votes
0 answers
101 views

Removing null production from cfg

While removing null production from cfg as below, S->ABC A->aA|^ B->bB|^ C->aaC|^ now as shown above we know that A,B and C all are ...
Zoha Javed's user avatar
0 votes
1 answer
117 views

How to Remove Left Recursion from this Grammar?

How to remove left recursion in the following Grammar: S→Bb/a B→Bc/Sd/e Im new to this, below is the way I'm doing it: ...
whoAsked's user avatar
0 votes
0 answers
40 views

Devising a grammar for language L = { a^xb^ya^xb^y | x, y >= 0 }

I've been trying to come up with a proper grammar for this sort of language: L = { aˣbʸaˣbʸ | x, y >= 0 } I have failed to find a way to enforce consistent generation of terminals on either part (...
MWR_'s user avatar
  • 1
1 vote
1 answer
44 views

Equivalence of LR(k) and LL(k′) parsers

Are there languages that can be parsed by an LR(k) parser but not by an LL(k′) parser for any k′?
Gator's user avatar
  • 11

1
2 3 4 5
26