Questions tagged [formal-grammars]
Questions about formal grammars, generative descriptions of formal languages.
971
questions
0
votes
2answers
22 views
How to prove this language is context free?
There's lots of ways to prove a language is not context free. Going through some exercises, I'm stuck at a question that asks me to prove that a language is indeed context free.
$L = \{a^{(n+1)} b^{(...
0
votes
1answer
16 views
Build LL(1) parsing table for grammar S -> iSeS | iS | a
Task
Bulid parsing table for grammar S -> iSeS | iS | a
Resolve conflicts in this table and simulate parser work for word ...
2
votes
1answer
124 views
What is the relation between parsing languages and checking languages?
I have looked at a number of textbooks on computability theory. They typically have the following form:
Define a language class (regular, context-free, context-sensitive, recursively enumerable)
...
1
vote
1answer
29 views
How to construct a CFG which generates {0, 1, #}⁺ - {b_1#b_2#b_3#… #b_n | n is a whole number} where b_i is i in binary without leading zeros?
This problem was originally given in "Introduction to Automata Theory, Languages and Computation" by John E. Hopcroft and Jeffrey D. Ullman as Exercise 4.3.
$$ \text {Let }b_i \text{ denote } i \text{...
2
votes
1answer
52 views
Formal Languages: if $L_1^* = L_2^*$, then $L_1 = L_2$
The question is: For all languages $L_1$ and $L_2$ , if $L_1^* = L_2^*$, then $L_1 = L_2$.
We know that two languages are equivalent if $L(G_1) = L(G_2)$, where $L(G) = \{w \in T^* \mid S\Rightarrow^*...
0
votes
1answer
25 views
What kind of Grammar could this be
I am trying to sort Grammar into the Chomsky Hierarchy and I can do so for most of my examples but I am stumped by the following one:
bX -> abY
which Type of ...
3
votes
1answer
31 views
Minimizing DFA built on set of words
A set of English words is given.
Is there linear or sublinear algorithm to build minimal DFA for the given dictionary?
I tried different approaches, and they all were concerned with building Trie and ...
2
votes
1answer
33 views
Set notation of a grammar
Say I have a grammar e.g,
$$\begin{align}S&\to AB\mid abc\\
A&\to aAb \mid \lambda\\
B&\to bBa \mid ba
\end{align}$$
Now it is obvious the notation for this would be something like,
$$L(...
10
votes
3answers
2k views
Representing “but not” in formal grammar
I just came across the following grammar definition:
CommentChar ::
SourceCharacter but not LineTerminator
But for discussion, I'll present this similar ...
0
votes
1answer
50 views
Table-Driven Lexer and the Classification Table
I'm trying to implement a compiler for a custom language as part of an assignment.
I am still trying to figure out how to build the lexer. From what I understand, for a table-driven lexer, we have 3 ...
4
votes
2answers
913 views
Generating random words by grammar
A bit of context
I was writing a parser for a grammar, and for testing purposes I come up with idea to generate some random inputs. The grammar I was dealing with was much more complicated, in this ...
4
votes
0answers
53 views
Reference on relating Post systems to string rewriting systems and formal grammars?
wikipedia states:
Every Post canonical system can be reduced to a string rewriting system (semi-Thue system). [...]
It has been proved that any Post canonical system is reducible to such a ...
0
votes
2answers
43 views
Formal grammar with constraints on the number of each symbol
I have a language where each type of symbol is only allowed a particular number of times, but the order isn't important. For example, lets say there are three symbols $a, b, c$, and a valid string in ...
-2
votes
0answers
27 views
Right-linear and left -linear Grammar
Could some explain what's the difference between right-linear grammar and left-linear grammar?
Maybe on this example:
$L:=\left\{w \in\{a, b\}^{*} | w \text { does not contain the subword abaab }\...
0
votes
1answer
24 views
Determining recursive enumerability of given languages
I came across following problem:
$L=\{M$ is a turing machine $M$ accepts two strings of different length $\}$
$L=\{M$ is a turing machine $M$ accepts atleast two strings of different length $\}...
1
vote
2answers
46 views
Is my grammar correct and context free?
I have this language
$L = \{a^{n}b^{3n}c^{2m} : m,n \ge 1\}$.
I have to determine a free context grammar that generates L.
Looks easy BUT i have a question about the grammar I found.
First things ...
0
votes
1answer
28 views
How to create CFG for $L := \{x| \#_0(x) \text{ is even and } \#_1(x) \text{ is odd}\}$
Create an CFG for all strings over {0, 1} that have the an even number of 0’s and an odd number of 1’s.
Also, I have a hint
HINT: It may be easier to come up with 4 CFGs – even 0’s, even 1’s, odd 0’s ...
-1
votes
1answer
28 views
Grammar for the following language: L = {$a^{k}$$b^{n}$$a^{m}$ : m,n,k $\in$$ N^{+}$ $\land$ m + k $\geq$ n}
I'm trying to create a grammar (having the highest type) for the language:
L = {$a^{k}$$b^{n}$$a^{m}$ : m,n,k $\in$ $N^{+}$ $\land$ m +k $\geq$ n}
I'm not finding any good approach for it. Hints ...
0
votes
1answer
38 views
CFG for $L=\{ \omega \in \{ a,b,c,d \}^* : |\omega|_a = |\omega|_b \}$
Given the language:
$$ L=\{ \omega \in \{ a,b,c,d \}^* : |\omega|_a = |\omega|_b \} $$
I propose the following grammar:
$$ \begin{align*}
S &\to \varepsilon \mid aSbS \mid bSaS \\
S &\to ...
1
vote
2answers
250 views
There exists an algorithm to find grammar of complement of a function?
I'm wondering if there exists an algorithm to solve the following problem:
Given a grammar $S$ of a context-free language $\mathcal{L}$, find a grammar
$S'$ such as $L(S) = L(S')^c $.
I note ...
0
votes
0answers
22 views
How to include both precedence and associativity in following grammar?
For the following grammar, how can I include both precedence and associativity of operators:
S -> S|S
S -> S.S
S -> S*
S -> (S)
S -> a|b
Note: In the first rule ...
0
votes
0answers
20 views
Find equivalent LL(1) grammar
There is sample question to calculate equivalent LL(1) grammar for below grammar:
$S \rightarrow S b$
$S \rightarrow S d$
$S \rightarrow c S$
$S \rightarrow c c a$
At first step, ...
0
votes
0answers
22 views
Dangling Else Ambiguous Grammar
How is the following grammar ambiguous
stmt -> if expr then stmt
| matched_stmt
matched_stmt -> if expr then matched_stmt else stmt |
terminal
3
votes
2answers
163 views
If L = {xy | |x| = |y|, x=y} is not Context Free, then what about L = {xy | |x| = |y|, x!=y}?
I know that, when x = y, then it's not Context Free. This is because, the first letter of y cannot be matched with first letter of x, which is at the bottom of the stack.
But, a link of Show that { ...
0
votes
0answers
29 views
Is this correct transformation of a grammar to one without left recursion?
So the last few days I am writing a compiler for a subset of C language by given grammar for a class at university. I encountered this problem and then I realized I need to remove left-recursion in my ...
0
votes
2answers
51 views
Is this correct grammar definition of Backus-Naur form?
I've been given a grammar definition of "Simple C language" in Backus-Naur to write a compiler for a class assignment. I've been trying to implement the parser for some time now and I just can't move ...
0
votes
1answer
60 views
What does {a,b}* for DFA's mean?
For instance when the question contains $\{a,b\}^*$ does this mean that the DFA must have at least one $a$ and one $b$ on top of whatever conditions it has?
For example a DFA that accepts $\{w \in \{a,...
0
votes
0answers
11 views
Detect a class of a grammar having its DSL AST
I have a grammar for some language written in some DSL for writing grammars, and this DSL implements EBNF. I have an AST for the description of a grammar in the DSL. How can I detect the minimal class ...
1
vote
1answer
47 views
Proof that language is not regular. $L=\{w\bar{w}|w\in \{0,1\}^* and\ \bar{w}\ is\ one's\ complement\ of\ w\}$
I'm trying to proof that the following language is not regular using pumping lemma.
$L=\{w\bar{w}|w\in \{0,1\}^* and\ \bar{w}\ is\ one's\ complement\ of\ w\}$
I started by stating that:
$|w\bar{w}| =...
1
vote
2answers
41 views
Context-free grammar for ${a^n b^n a^n}$
I am trying to figure out a formal grammar for the above language. This language describes palindromes, so it is context-free, if I am not wrong. I came up with a context-sensitive grammar, but I can ...
0
votes
1answer
32 views
Is this grammar LL(1) grammar?
Is this grammar LL(1)? Would it be a problem that S can be both E/S and E?
S -> E / S
S -> E
E -> letter
E -> ‘ S ’
Can it derive ‘a / e / ‘g / s’ ’...
0
votes
0answers
56 views
I´m having problems with this Context Free Grammar
I am not able to convert the following language to a Context Free Grammar. The major problem is how to pump both "sides" of the word to obtain same number of 0s and 1s, but, without creating a series ...
0
votes
1answer
22 views
Textbook for understanding formal grammars
I am looking to understand the Chomsky Hierarchy. I've read some textbooks that touch on formal grammars (textbooks on computability, which relate automata to specific sets of formal grammars, notably ...
0
votes
1answer
97 views
Why LL(1) grammar generate all regular languages?
I came across following:
Every regular language has right linear grammar and this is LL(1). Thus, LL(1) grammar generates all regular languages.
I tried to get that.
Definition: Right linear ...
0
votes
1answer
34 views
Adding constraints in grammar for Grammatical Evolution
I'm trying to use Grammatical Evolution for creating trading strategies. Each sentence in the grammar when evaluated gives a weight matrix of size n x p . (n is the length of backtesting period and p ...
0
votes
1answer
15 views
Ambiguous Grammar demostration exercise
Hi im stuck on an exercise of ambiguous grammar. I need an example that shows that this grammar is ambiguous. The grammar is defined as follows:
$$S \rightarrow aT | bR$$
$$R \rightarrow a | aS | bRR$...
1
vote
1answer
35 views
How to write grammar production rules to describe recursive structures?
I'm trying to describe a data structure by production rules. The structure is recursive; say a list of type $A$ made of elements of type $A$ or $B$.
Writing the grammar, I build this:
$(S \...
2
votes
1answer
33 views
How does $LL(n)$ languages compare with $LR(0)$, for $n>0$?
In the context of languages (not grammars), I know following:
$LL(0) \subset LL(1) \subset LL(2) \subset \cdots \subset LL(k)$
$LR(0) \subset SLR(1) = LALR(1) = LR(1) = SLR(k) = LALR(k) = LR(k)...
2
votes
2answers
93 views
Grammar with fewest variables
I am looking over a past exam for a theory of computation class I am taking, and unfortunately no solutions are provided. I am stuck on this question, and would greatly appreciate any help or hints.
...
1
vote
1answer
39 views
Find a Context-Free Grammar for $L:=\{a^nb^mc^{n+m}\mid n,m\in\mathbb{N}\}$
I want to find a Context-Free Grammar for $L:=\{a^nb^mc^{n+m}\mid n,m\in\mathbb{N}\}$
I've tried the following:
$G=(V,\Sigma,R,S)$ with $\Sigma=\{a,b,c,\lambda\}$, $V=\{S,B\}$, $S=S$ and $$R=\{S\to \...
0
votes
1answer
129 views
Convert ambiguous grammar to unambiguous and SLR(1)
I have the following ambiguous operator grammar:
E->E+E*E | E-E*E
E->E+E | E-E | E+E | E*E | E/E
E->(E) | x
I must convert it to an unambiguous one ...
1
vote
0answers
31 views
Deciding whether CFG generates the empty word
Give an algorithm to decide the following problem: given
a CFG $G$, does $G\Rightarrow^\star \epsilon$? That is, given a grammar can it
generate the empty word? How can I make sure my algorithm is ...
0
votes
0answers
74 views
Grammar for language L on {a, b} where L = {w|na(w)mod 3 = 0} [duplicate]
I am able to form the regular expression but I am not confident with the grammar.
I have tried the following:
S-->aaaS|bS|b|lambda
Regular expression is given by:
...
2
votes
1answer
324 views
How to simplify context free grammars?
How to simplify this context-free grammar?
$$
S \to ACD \\ A \to a \\ B \to \varepsilon \\ C \to ED \mid \varepsilon \\ D \to BC \mid b \\E \to b
$$
Can the simplification result in this CFG?
$$
S \...
2
votes
1answer
88 views
Context-free Grammar Exercise
Could someone explain me how to form a context-free grammar with all rules R by this example language, please?
\begin{equation}
L:=\left\{w c v c \overleftarrow{w} | w, v \in\{a, b\}^{+}\right\}
\end{...
3
votes
2answers
160 views
Give a grammar for a language on Σ={a,b,c} that accepts all strings containing exactly one a
I have created the following solution but its left recursive:
S--> a|bSc|cSb|Sbc
Also it is not accepting:
"ab" or "cba" or "abb" or abc.
Somebody please guide me.
Zulfi.
1
vote
2answers
31 views
Useless production
Kindly consider the following productions. How can I identify a useless production?
S->aS|A|C
A->a
B->aa
C->aCb
Somebody please guide me.
Zulfi.
0
votes
1answer
72 views
How to convert the left recursive grammar into right recursive grammar
I have a grammar: $A\rightarrow Aa|bB|c$
The above is the left recursive grammar.
I understand that I have to remove the string "Aa" from the above grammar or to convert it into the form "aA" to ...
3
votes
0answers
162 views
Proper algorithm for resolving ambiguity in grammars via enforcing associativity and precedence rules
I was told there is a algorithm that always resolves ambiguity for grammars that have issues with precedence and associativity. I know ambiguity in general is undecidable, so I only want to resolve ...
1
vote
1answer
25 views
What does the term “top-most” mean in the context of formal grammars?
I was learning about disambiguating grammars. In particular I was learning about enforcing right associativity on the sum language here:
$$ \mathit{Sum} ::= 0 \mid 1 \mid \mathit{Sum} + \mathit{Sum} \...
