Questions about formal grammars, generative descriptions of formal languages.
1
vote
1answer
14 views
CNF: Recursion in CFG
How can I deal with recursive terminals in CFG when converting it to CNF? For example,
S -> MN
M -> AM | A
N -> BN | B
A -> a
B -> b
How can I reduce terminals M and N?
2
votes
4answers
58 views
Grammar that numbers of letters `c` is greater than number of letters `b`
Exactly as stated in the subject. I look for grammar which use letters $a, b ,c$ that numbers of letters $c$ is greater than number of letters $b$.
Example: $acbccba$ is generated by the grammar.
I ...
0
votes
0answers
23 views
Grammar that contains letters a,b,c and number of letters $c$ is greater than number of letters $b$ [duplicate]
I look for grammar which use letters $a,b,c$ that numbers of letters $c$ is greater than number of letters $b$.
Example: $acbccba$
I thought about:
$$S \rightarrow aS \mid bS \mid SCS$$
$$C ...
0
votes
2answers
41 views
Can this grammar be simplified?
So, I have a book here, which has an example for context sensitive grammar, and the grammar is the famous $0^n1^n2^n$ , and it has:
$$ \begin{align}
S &\rightarrow 0BS2 \mid 012 \\
B0 ...
1
vote
2answers
65 views
Easiest way to write a grammar?
When I see a problem like "Write a grammar for a language $L$ if $L = \{..\}$" for me is a matter of "instinct" the way that one can define productions. For example given the following exercise:
...
1
vote
2answers
103 views
Converting CFG to PDA
I have the following CFG,
$S \rightarrow CB$
$C \rightarrow aCa \text{ }|\text{ } bCb \text{ }|\text{ } \text{#}B$
$B \rightarrow AB \text{ }|\text{ } \varepsilon$
$A \rightarrow a\text{ }|\text{ }b$
...
1
vote
0answers
47 views
Negative lookahead in LR parsing algorithm
Consider such a rule in grammar for an LR-family parsing generator (e.g YACC, BISON, etc.):
Nonterminal : [ lookahead not in {Terminal1, ..., TerminalN} ] Rule ;
...
2
votes
1answer
62 views
How to show that L = L(G)?
Specifying formal languages by giving formal grammars is a frequent task: we need grammars not only to describe languages, but also to parse them, or even do proper science. In all cases, it is ...
1
vote
1answer
50 views
Size of a context-free grammar
Is there a formal definition for a size of a context-free grammar? The only definition I have seen so far is on this wiki page:
The size of a grammar is the sum of the sizes of its production ...
0
votes
1answer
64 views
Convert CFG to PDA
Is there any set of rules or methods to convert any context free grammar to a push down automata?
I already found some slides online but I wasn't able to understand them.
In slide 10 he speaks ...
0
votes
0answers
29 views
Is this Chomsky Normal form correct? [closed]
Here is my approach, am I right?
Chomsky Normal Form solution for a problem
Here is my attempt at CNF,
...
0
votes
1answer
43 views
Simple FSM question
Considering this FSM:
Can someone explain me why the grammar is not:
$S \rightarrow aA$
$A \rightarrow aA \mid bB \mid \varepsilon$
$B \rightarrow bB \mid \varepsilon$
Why does A not have a ...
4
votes
1answer
44 views
Closure under intersection of context free binary trees
Some sets of ordered binary trees can be represented as a CFG with rules of the form
A -> aBC
A -> b
Where A,B,C are ...
0
votes
1answer
37 views
CFG for $\{a^i b^j : 2 i<j\}$ [duplicate]
So I have a question:
Give a CFG for $\{a^i b^j : 2 i<j\}$
And this is my approach:
$S\to AB$
$A\to aAb\mid \varepsilon$
$B\to b \mid bB$
A confirmation, or correction, along with how you ...
2
votes
1answer
22 views
Chomsky form for language of single alphabet member
I'm a bit confused as to how to represent the Chomsky form for the language L that generates all strings with the alphabet {a}
My approach was
...
2
votes
2answers
73 views
Context free grammar construction
My problem with CFG is, I am to generally create ones that don't have requirements such as:
$\qquad \{a^m b^n \mid m \le n \le 2m \}$
I have no clue where to begin, and how to approach it. I was ...
1
vote
2answers
49 views
How to write Context Free Grammar with numerical restrictions
I am supposed to write a Context free grammar that generates the language:
$\qquad L(G) = \{0^{3n}1^{2n}0^{m}1^{m} : n \ge 1, m \ge 1\}$
I have the rules:
$$S \rightarrow 000S$$
$$S \rightarrow ...
5
votes
2answers
94 views
Finding the language generated by a context-free grammar
This is a question from the Dragon book (I apologize for translation mistakes, I don´t have the English version on hand):
What language is generated by this grammar?
$S \rightarrow a S b S ...
1
vote
2answers
82 views
Grammar for describing boolean expressions with AND, OR and NOT
I wrote the following LL(1) grammar to describe the set of boolean expressions involving AND ,OR an ...
-1
votes
1answer
117 views
Is the following grammar ambiguous?
Is the following grammar ambiguous and how would you justify it?
$G=(\{ S,A,B \}, \{a,b\},\{S \to aA, A \to BA \mid a, B \to bS \mid cS\}, S)$
2
votes
2answers
69 views
The importance of normal forms like Chomsky normal form for CFGs
I understand that context-free grammars can be used to represent context-free languages.It might have ambiguities. We also have normal forms like Chomsky and Greibach normal form. I couldn't ...
1
vote
1answer
59 views
Is the following language context free?
Is $L = \{ a^nb^nc^j \mid n \le j\}$ a context-free language? I'm getting really stuck generating a grammar for it. Any help would be appreciated.
0
votes
1answer
32 views
CFG using the set $L =\left\{{a,b}\right\}$ for the expression $a^{m}b^{n}$, where $m \neq n$ [duplicate]
I need to find a context-free grammar for the above expression, $a^{m}b^{n}$ for the set $L = \left\{{a, b}\right\}$, but I am having difficulty accounting for the condition $m \neq n$.
This is what ...
1
vote
1answer
60 views
CFG to Chomsky normal form
I've read this part like 3-4 times and I'm not understanding what is going on.
Let G6 be the following CFG and convert it to Chomsky normal form by using the conversion procedure just given. The ...
5
votes
4answers
167 views
What is the exact relation between programming languages and Turing machines?
I don't know much about yacc, bison, flex or lex and please correct me if I'm wrong but a programming language is also a Turing machine and a Turing machine is defined as the tuple $(Q, \Gamma, b, ...
2
votes
1answer
63 views
Lookahead set: Determining minimum $k$ such that $G$ is a strong $LL(k)$ grammar
How do we determine minimum $k$ such that $G$ is a strong $LL(k)$ Grammar
Like for grammar $G$ with the following rules
$S\rightarrow aAcaa \mid bAbcc,A\rightarrow a \mid ab \mid \epsilon$
4
votes
2answers
60 views
Priority in formal grammar
From my recitation class, I have the following exercise:
$\mathrm{EXP} = 0 \mid 1 \mid b \mathrm{EXP} \mid \mathrm{EXP} a \mid \mathrm{EXP} m \mathrm{EXP}$
The above grammar is ambiguous.
...
7
votes
2answers
97 views
Decidable languages and unrestricted grammars?
Turing machines and unrestricted grammars are two different formalisms that define the RE languages. Some RE languages are decidable, but not all are.
We can define the decidable languages with ...
4
votes
0answers
116 views
Shift-resolve parsing - questions
I've recently came across a paper describing the parsing technique
mentioned in the title. Unfortunately, the terminology used in said paper
is somewhat beyond my comprehension, so I've been ...
1
vote
1answer
51 views
Are there languages generated by linear grammar which aren't regular?
Are there languages generated by linear grammer which aren't regular?
-1
votes
1answer
54 views
Constructing right-linear grammar
Is the grammar
$\qquad S \to 1A0A \mid 0A \mid \varepsilon$
a right-linear grammar? $A$ is a nonterminal here, $0$ and $1$ are terminals.
I know $0A$ is right-linear but what about $1A0A$?
Trying ...
3
votes
2answers
220 views
Why is left recursion bad?
In compiler design, why should left recursion be eliminated in grammars? I am reading that it is because it can cause an infinite recursion, but is it not true for a right recursive grammar as well?
3
votes
1answer
30 views
How to define at least one occurrence of a string between two tokens in bottom up LALR(1) parser grammar
I am trying to define a non terminal symbol in a LALR(1) grammar (with CUP parser). It is requested that
...
0
votes
1answer
171 views
Context Free Grammar for language L
Can someone help with this:
$L=\{a^ib^j \mid i,j \ge 1 \text{ and } i \ne j \text{ and } i<2j\}$
I'm trying to write a grammar for this language?
I tried this:
$S \to S_1 \mid S_2 \\
S_1 \to aXb ...
2
votes
2answers
156 views
Context Free Grammar for language $L=\{a^ib^j \mid i,j \ge 0; i \ne 2j\}$
Can someone help with this:
$L=\{a^ib^j \mid i,j \ge 0 \text{ and } i \ne 2j\}$
I'm trying to write a grammar for this language?
I don't know how to do this.
I tried this:
$S \rightarrow aaAb ...
2
votes
1answer
87 views
Is the ambiguity of a regular tree grammar decidable?
Is there an algorithm which decides whether a regular tree grammar $G$ is ambiguous, i.g. there exists a tree $t\in L(G)$ which can be parsed by the grammar in more than one ways, using only leftmost ...
3
votes
3answers
177 views
How to convert a context free grammar (could generate regular language) to a right-linear grammar
Consider the context free grammar:
$$S \rightarrow aSb \mid aSa \mid bSa \mid bSb \mid \varepsilon$$
It could generate regular language, which means it can be converted to a right linear grammar.
Is ...
1
vote
2answers
104 views
Can a CFG end have a non-terminal symbol in the middle of it?
What is the correct way to write a CFG?
A -> B C' E
C' -> C
C' -> null
or
A -> B C'
C' -> C E
C' -> E
4
votes
3answers
92 views
Give a grammar to show whether a language is regular or context-free
I have to generate a grammar for the language $L = \{ w \in \{ a, b\}^* \mid |w| \in 2\mathbb{N}, w \neq w^R\}$ and give the type of the language.
I've generated the grammar
$\qquad \begin{align}
...
2
votes
1answer
32 views
Is there a name for this relation on CFGs?
I'm looking for the name (or a name if there isn't one already) of this relation between $G_1=\left<\Sigma_1,\mathcal{N}_1,\mathcal{R}_1,S_1\right>$ and ...
1
vote
1answer
86 views
Construct a context-free grammar for a given set of words
I have seen a few years back a nice and simple algorithm that, given a (finite) set of words in some alphabet, builds a context-free grammar for a language including these words and in some sense ...
0
votes
0answers
44 views
How i can use Mathematical induction to prove CFG production? [duplicate]
If I have production $G_n$
$S \rightarrow A_i b_i \quad$ for $1 \le i \le n$
$A_i \rightarrow a_j A_i \mid a_j\quad$ for $1 \le i$ and $i \ne j$
Prove $G_n$ is sub-productions from $2n^2 ...
0
votes
1answer
77 views
Show how a sentence can be produced from a grammar (Dragon book 2.1)
In the Dragon book (Aho, Sethi, Ullmann) there is one exercise I don't get.
Chapter 2, Exercies: 2.1
Given the context-free grammar
$$S \to S S + \mid S S * \mid a$$
Task: Show how the signs ...
0
votes
2answers
294 views
Regular Expression to Context-Free Grammar
Anyone knows if there is an algorithm for directly write the context-free grammar that generates a given regular expression?
2
votes
4answers
315 views
Roman Number is ambiguous language?
An ambiguous Language is a formal language for which there exists a string that can have more than one meaning (several possible meanings or interpretations). Multiple synthesis structures for a ...
0
votes
1answer
79 views
Pumping lemma for Context-Free Languages
I have a question about a specific pumping lemma problem for Context-Free Languages.
Suppose we have the following Language:
$L = \{a^{i}b^{j}c^{k}d^{l} \mid 0 < i < k \wedge j > l > ...
1
vote
1answer
39 views
Demonstrating that for every monotonic grammar there is an equivalent context-sensitive grammar
I'm trying to understand the equivalence in expressive power of formal grammars whose rules take the form:
$$ \alpha \rightarrow \beta $$ where $ |\alpha| \leq |\beta| $ (called a monotonic grammar), ...
5
votes
3answers
240 views
Can someone give a simple but non-toy example of a context-sensitive grammar?
I'm trying to understand context-sensitive grammars.
I understand why languages like
$\{ww \mid w \in A^*\}$
$\{a^n b^n c^n \mid n\in\mathbb{N}\}$
are not context free, but what I'd ...
2
votes
2answers
157 views
Finding the grammar type of the programming language
How can someone find what type of grammar for a given programming language?
Formerly I'm looking for a grammar type for most popular programming languages: C, C++, C#, Java, List, OCaml, Haskell etc.
...
4
votes
2answers
109 views
Is this grammar really LL(1) while not being LR(1)?
$S \rightarrow S$, $L(G) = \{\}$
LL(1) analysis:
We estabilish $FIRST(S)$ to be empty and $FOLLOW(S)$ to be $\{\$\}$.
$FIRST(S)$ doesn't contain ε, so the parse table looks like this:
...
