Questions about formal grammars, generative descriptions of formal languages.
2
votes
1answer
62 views
Are the languages $\{w\in \{a,b\}^* : \#_a(w) > \#_b(w) \}$ and $\{w\in \{a,b\}^* : \#_a(w) \neq \#_b(w) \}$ context free?
So at the beginning I was aiming at $L_{a\neq b} = \{w\in \{a,b\}^* : \#_a(w) \neq \#_b(w) \}$. But figured out that is would be better to first deal with: $L_{a>b} = \{w\in \{a,b\}^* : \#_a(w) &...
1
vote
0answers
21 views
Grammar for invertible functions
Has anyone ever come up with a grammar that only induces invertible functions, and does so in a way where it is possible to algorithmically construct the inverse function? It could be useful for ...
1
vote
1answer
30 views
Words generated by CFG whose parse tree contain even number of $X$
Let $G$ be a context-free grammar with set of terminals $A$. Let $X$ be a non-terminal in $G$. Is the language of words over the alphabet $A$ with a syntax tree in which the non-terminal $X$ appears ...
2
votes
1answer
42 views
Context formal language recognizing even number of 0's and odd number of 1's
I have an assignment, it's asked to write a context free grammar recognising the language $L=\{ w \mid w\text{ has an even number of }0\text{s and an odd number of }1\text{s}\}$, over the alphabet $\{...
1
vote
1answer
77 views
How to transform lambda function to multi-argument lambda function and how to rewrite or approximate terms?
I am trying to do the formal semantics (Montague grammar, abstract categorial grammar) of natural language and encode the sentence John is boss. The type system has ...
1
vote
1answer
33 views
Using a context free grammar to generate sample utterances for Amazon Alexa/Google Assistant?
I would like to get some opinions about using a context free grammar to generate sample utterances for Amazon Alexa/Google Assistant skills.
When developing these skills one has to provide a large ...
1
vote
1answer
33 views
What is handle in bottom up LR parsing?
I was taking course on compilers by Alex Aiken. You can find the slide discussing handles on this page. On the page of the slide, the instructor defines handle as follows:
Assume a rightmost ...
0
votes
1answer
46 views
Define a grammar to emmulate chess rules
Is it possible to define a 《chess language》:
language={alphabet = {(chess pieces, squares of chess board)}, grammar={rules of movement of pieces over the board}}?
I looked online but I cannot find a ...
1
vote
1answer
49 views
Formal grammar with variables for consistent substitutions
In a rewriting system, suppose the production rule S→xAyAz (or <S>:=x<A>y<A>z, in BNF), where S and A are ...
0
votes
0answers
23 views
Chomsky Normal Form (Removing Unit Production)
Remove unit and null productions...
$$
\begin{align}
S &\rightarrow Ua \\
U &\rightarrow aUbb\mid S\mid \epsilon
\end{align}
$$
Removing null production ($U \rightarrow \epsilon$) first ...
2
votes
0answers
18 views
Intuition on what an attribute grammar can achieve
I have seen attribute grammars for a small handful of tasks:
Parsing simple arithmetical expressions
Type checking
Checking that a variable is initialized
anbncn (seems to be a favorite toy example).....
1
vote
1answer
79 views
0
votes
1answer
36 views
Context-free grammar for $L=\{0^n1^{2n} \mid n \geq 0\}$ [closed]
How can I express this language $L = \{0^n 1^{2n} \mid n ≥ 0\}$ as a context-free grammar?
I am new to this field and I am not sure what should I do. Please help me.
0
votes
1answer
36 views
Different context-free grammars for the same language
In context-free grammar, are both the following grammars correct for the same language?
$$L = \{a^mb^n : m, n \in N_0 \text{ and } m \ne n\}$$
(grammar one)
$S \to S_1 | S_2$
$S_1 \to A_1B_1$
$...
0
votes
1answer
50 views
Can you automatically generate a parser for a type using type theory some how?
Was wondering since all the types are spelled out constructively, and the constructions can all be reflected symbolically on a computer, if you can automatically parse expressions in a type?
1
vote
1answer
29 views
Right definition of linear grammar
I was referring book by Peter Linz, which defines linear grammar as follows:
A linear grammar is a grammar in which at most one variable can occur on the right side of any production, without ...
0
votes
0answers
13 views
Equivalent grammar in Chomsky Hierarchy [duplicate]
I want to know if given a grammar, for example, a context-sensitive (type 1) can it always be "reduced" to a equivalent context-free grammar (type 2) and so on for grammars type 2 to "reducing" and ...
0
votes
0answers
57 views
Is a Turing Machine able to reduce a grammar by chomsky hierarchy? [duplicate]
If given a grammar, for example, a context-sensitive (type 1) can it always be "reduced" to a equivalent context-free grammar (type 2) and so on for grammars type 2 to "reducing" and getting a type 3?
...
0
votes
1answer
43 views
Is it possible for a Turing machine to be able to reduce a grammar and tell where it fits in chomsky hierarchy?
For example:
This looks like a context free grammar:
𝑆 → 𝑄𝑅𝑇
𝑄 → 𝑎𝑄 | 𝑎
𝑅 → 𝑏𝑅 | 𝑏
𝑇 → 𝑐𝑇 | c
but it can be reduced to this regular language:
𝑆 → 𝑎𝑆 | 𝑎𝑅
𝑅 → 𝑏𝑅 | 𝑏𝑇
𝑇 → 𝑐𝑇...
0
votes
0answers
13 views
What production rules produce propositional logic tautologies?
Production rules correspond to Turing machines:
[U]nrestricted grammar[s]...can generate arbitrary recursively enumerable languages.
There is a Turing machine that can recognize tautologies in ...
1
vote
1answer
43 views
0
votes
0answers
28 views
Conversion from automaton to left linear grammar
I stumble across this problem:
Give right linear grammar.
The solution given was simple:
$S\rightarrow bA$
$S\rightarrow aS$
$A\rightarrow \lambda$
$B\rightarrow bA$
$A\rightarrow aB$
Earlier ...
3
votes
1answer
150 views
Understanding application of Arden's theorem to find regular expression
I learnt Ardens theorem and its usage as follows:
Ardens Theorem
Let $P$ and $Q$ be two regular expressions over alphabet $Σ$. If $P$
does not contain null string, then $R = Q + RP$ has a ...
0
votes
0answers
19 views
How many sets of LR(0) items exist in this grammar? (question from the dragon book)
The grammar:
\begin{align}
S&\rightarrow A_ib_i &\text{for }1\le i\le n\\
A_i&\rightarrow a_jA_i\mid a_j &\text{for }1\le i,j\le n\text{ and } i\neq j
\end{align}
The answer is $2^n +...
1
vote
1answer
50 views
Context Free Grammar $L = \{a^i(b+c)^jd^k | i<j+k; i,j,k>0\}$
I'm trying to design a CFG that accept the words of the following language:
$$L = \{a^i(b+c)^jd^k \mid i<j+k; \quad i,j,k>0\}$$
My first approximation would be to do $i = j+k$ as something ...
0
votes
0answers
19 views
Transform grammar into LL(1) left-associative
I was looking on some old exam questions for a course in my university, and stumbled upon an exercise that asked for the following: The starting grammar was this:
...
0
votes
1answer
27 views
Why is this grammar an LL(2) grammar?
I had a question regarding LL($k$) grammars. I came across a problem that I attempted to solve, but my answer varied from the solution and I wasn't sure why.
$$L = \{a^{n + 2}b^mc^{n + m}\ :\ n \ge 1,...
0
votes
1answer
94 views
Does adding S->SS in a context-free grammar change the language to its Kleene star?
Let $L$ be the language generated by a context-free grammar whose start variable is $S$. Does adding $S \rightarrow SS$ in this grammar creating language $L^*$, why? What about grammars in Chomsky ...
0
votes
0answers
24 views
How to convert LL to RR grammar?
I need to convert the LL grammar to LR? I am a noobie in this question. I found an algorithm to remove a left recursion but I'm not sure it will convert it in the RR grammar...
Can anyone advice ...
0
votes
0answers
28 views
Prove this Context-Free Grammar is Ambiguous
so I have a problem on one of my computational structures final reviews, and I cannot seem to figure it out. It's been driving me crazy, so I would like to post it here for some insight.
Prove that ...
-1
votes
2answers
46 views
Context-free grammars for two languages
How do I write context-free grammars for the following languages?
$B_2 = \{0^n1^n \mid n > 0\} \cup \{0^n1^{2n} \mid n > 0\}$
$B_3 = \{a^nb^mc^k \mid k = n+m\}$
Can someone help me? I'm not ...
3
votes
1answer
178 views
This doesn't seem like a valid regular grammar; my instructor says it is
The following is a screenshot of a lecture slide from my programming language concepts course:
According to Wikipedia and other sources, a regular grammar is one that is either left linear or right ...
-2
votes
1answer
36 views
Context free languages [closed]
I have stumbled on this question:
Which of the following languages over the alphabet ${a,b,c,d}$ are context-free and which not ?
a) $L_{1} = \{wa^{3n+1}b^nw^{R} \mid w\in \{c,d\}^*,\ n>0\}$;
b)...
0
votes
0answers
12 views
How to convert this CFL into a CFG? [duplicate]
I'm trying to convert the following context free language into a context free grammar.
$L = \{a^i b^j c^k \,|\, i+2j=4k;\, i, j, k ≥ 0\}$
I am struggling given the fact there is a large number of ...
3
votes
2answers
83 views
Why is the start symbol “not allowed” on the right hand side in Chomsky normal form?
I had a question regarding CNF (Chomsky normal form) in formal language theory.
I noticed that a lot of authors (including my own professor, and the Wikipedia page for CNF) frown upon or don't allow ...
0
votes
0answers
33 views
If a Triple Graph Grammar rule counts as a Mathematical Proof
I am intrigued by Triple Graph Grammars (TGG) as a potential for formal mathematical proof.
Triple Graph Grammars (TGGs) are a technique for defining the
correspondence between two different ...
4
votes
1answer
36 views
Removing lambda-productions when it's at the start symbol
I had a question regarding removing lambda-productions from context-free grammars.
I understand that the basic theorem or process for removing lambda-productions is to find nullable productions and ...
0
votes
0answers
17 views
Regular grammar question [duplicate]
Define a regular expression such that there is a string of 1 or more a's continuous followed by a continuous string of b's so that the number of a's and b's are the same.
I have ideas on how i would ...
0
votes
2answers
96 views
Making a CFG for a^i b^j c^k such that i+j = 3k
I have the language $L = \{a^i b^j c^k \mid i+j=3k\}$, however I am struggling to convert it to a CFG.
I have made it into a PDA fairly easily, its just now getting this to the CFG which is the issue....
1
vote
1answer
30 views
What do two non-terminal symbols on the left hand side of a BNF grammar mean?
I'm learning BNF, and the text I'm using gives a simple grammar for integer expressions like this:
...
1
vote
1answer
26 views
How do I build a left derivation tree from an expression including right-to-left associativity?
Suppose I want to make a left derivation tree of an expression, but the expression includes operators that are right-to-left associative. Would I still expand the left-most variable first in my tree? ...
0
votes
0answers
38 views
When proof by induction on length string is not possible?
I found out an exercise where you have to prove the correctness of the following CFG:
Let $L=\{ 0^i 1^j|2i \leq j \leq 3i \}\:$ and
$\: G: S\rightarrow 0S11 | 0S111| \epsilon$
claim: Every string $w ...
-1
votes
1answer
72 views
Write a grammar for a language $L=\{ba^{2^n}b |n\ge 1\}$ [closed]
Write a grammar for a language $$L=\{ba^{2^n}b | n\ge 1\}.$$ It's not even context-free as I think. I just can't produce it, although I've tried a lot.
Now my best attempt is:
\begin{aligned}
S &\...
0
votes
0answers
26 views
How can i define left-recursions?
I'm new with parsing and I already understood (finally) how I can go from
A -> Bxy | x
B -> CD
C -> A | c
D -> d
to
...
1
vote
1answer
50 views
Proving that a context-free grammar is unambiguous [duplicate]
I have to find an unambiguous context-free grammar that generates the following language. $$L= \{ w \in \{a,b\}^+ : |w|_a = |w|_b\}$$
I think I have found the context-free one, it should be this one.
$...
0
votes
0answers
22 views
Value of k for the LL grammar?
For the language, a^n b^m c^n+m and the grammar
\begin{align*}
S&\to aAc \\\
A &\to aAc \mid bBc\\
B &\to bBc \mid \lambda
\end{align*}
What would the value of k be since this is an LL(k)...
0
votes
1answer
37 views
Does this constitute as an LL grammar?
For the language, $L(aa^*ba) \cup L(abbb^*)$ and the grammar
\begin{align*}S&\to aAba \mid abbB\\
A &\to Aa \mid \lambda\\
B &\to Bb \mid \lambda
\end{align*}
Would the grammar above ...
2
votes
0answers
23 views
Give LL grammar for this language?
I need to give the LL grammar for the language below and explain why the grammar is LL and what the value of $k$ should be:
$$L = \{ a^n c^m c^{n+m} : n \ge 1, m \ge 1 \}. $$
I have the following, ...
0
votes
0answers
30 views
Operator-precedence grammar
I can't get what is the operator-precedence grammar... I need to convert this grammar to the grammar of weak precedence but I can't get it even.
What does this notation mean ...
1
vote
0answers
63 views
Is star closure of reverse of grammar equivalent to reverse of closure of that grammar
I need to proof if that it's true or not. $ (G^R)^* = (G^*)^R $
If $G$ is a CFG and $ G = \langle V, \Sigma, \delta, S \rangle $ where
$ V $ = Set of Variables or Non-Terminal Symbols
$ \Sigma $ = ...
