Questions tagged [formal-grammars]
Questions about formal grammars, generative descriptions of formal languages.
1,282
questions
1
vote
1
answer
33
views
Detect (indirect) left-recursion in a context-free grammar?
Given a context-free grammar:
A -> α0 | α1 | ...
B -> β0 | β1 | ...
...
It's straightforward to determine whether the grammar is directly left-recursive - it ...
- 151
2
votes
2
answers
476
views
Do all instances of a given string get replaced under a rewrite rule?
I am doing a course in uni on Automata and Formal Languages, and I think I've come across a pretty significant misunderstanding. When you have a rewrite rule in a grammar, and apply it to a string, do ...
4
votes
1
answer
59
views
Proving that two languages both represent valid bracket sequences
I have two languages $L_1$ and $L_2$, both subsets of $\{0, 1\}^*$, defined as follows:
For $L_1$, we have that
$01 \in L$
If $w \in L$, then $0w1 \in L$
If $w_1, w_2 \in L$, then $w_1w_2 \in L$
For ...
3
votes
0
answers
118
views
Convert a regular expression to a *minimal* LL(1) regular grammar
Given a regular language defined by a regular expression, we can convert it to an NFA, which is equivalent to a right-regular grammar. The grammar is not generally LL(1).
However, if we convert the ...
- 151
1
vote
1
answer
58
views
Give a class of languages which is closed under intersection and union, but not under complement
I am pondering this question, it is posed early on in a course on Formal languages and Automata, but before much progress has been made on closure of Regular and Context Free languages under ...
3
votes
1
answer
201
views
Understanding a bound for derivation length of any string in Pumping lemma for context-free languages
The following is a proof of the pumping lemma for context-free languages from Theorem 8.1 in "An Introduction to Formal Languages and Automata (6th ed.)" by Peter Linz:
Let $L$ be an ...
- 137
1
vote
1
answer
55
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) ...
- 33
1
vote
0
answers
54
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:
...
1
vote
0
answers
32
views
Effect of slight modification to LL(1) parse table generation
I am experimenting with LL(1) parsers that do not use a separate lexer.
I have the following grammar:
S = (('<' S '>' | 'a'+) ' '?)+
The notation uses ' ...
- 11
0
votes
1
answer
31
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 ...
- 123
2
votes
2
answers
51
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 ...
- 163
-1
votes
2
answers
112
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 ...
- 139
1
vote
0
answers
13
views
Why would a control flow block need access to the labels associated with a higher or lower level nested control flow block?
In Engineering a Compiler (Cooper, Torczon) 3rd Edition, Chapter 5 Syntax-Driven Translation, Section 5.3.3 Translating Control-Flow Statements, the following nested control-flow grammar is presented,
...
- 31
1
vote
0
answers
12
views
Why must empty rules be inserted in syntax-directed translation of a control-flow grammar?
In Engineering a Compiler (Cooper, Torczon) 3rd Edition, Chapter 5 Syntax-Driven Translation, Section 5.3.3 Translating Control-Flow Statements, the following nested control-flow grammar is presented,
...
- 31
0
votes
1
answer
38
views
0
votes
0
answers
19
views
is there a way to eliminate indirect left recursion of this grammar?
I have an indirect left recursive grammar: expr_1 := expr_1 ...
...
0
votes
1
answer
21
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 ...
0
votes
0
answers
52
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 ...
0
votes
0
answers
23
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 ...
- 61
0
votes
1
answer
64
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 ...
- 359
0
votes
0
answers
50
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" ...
- 111
0
votes
1
answer
55
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 [,].
...
- 103
1
vote
0
answers
80
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
...
- 33
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), ...
- 352
0
votes
1
answer
42
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 ...
- 1,549
0
votes
3
answers
74
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 ...
- 111
0
votes
3
answers
68
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 ...
- 183
-1
votes
2
answers
64
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 ...
- 365
4
votes
0
answers
128
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 ) ...
1
vote
2
answers
93
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 ...
- 23
0
votes
1
answer
40
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 ...
- 29
3
votes
1
answer
66
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 ...
- 1,549
0
votes
0
answers
66
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
...
- 275
3
votes
1
answer
319
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 ...
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(...
- 195
1
vote
0
answers
25
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 ...
- 111
1
vote
1
answer
71
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: $...
- 23
0
votes
1
answer
401
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 ...
- 23
1
vote
1
answer
55
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 ...
- 11
1
vote
0
answers
22
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 ...
- 111
2
votes
2
answers
176
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 ...
- 21
0
votes
0
answers
28
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 ...
- 1
1
vote
1
answer
65
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 ...
- 77
1
vote
0
answers
22
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 ...
- 111
5
votes
1
answer
490
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 ...
- 77
0
votes
1
answer
35
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$ ...
- 13
0
votes
1
answer
94
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 ...
- 23
1
vote
0
answers
118
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 ...
- 111
1
vote
1
answer
90
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?
- 94
0
votes
1
answer
71
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 ...
- 1