Questions about formal grammars, generative descriptions of formal languages.
0
votes
1answer
23 views
Closure properties between two languages from different grammars
We know that if we have two languages produced by one regular grammar, then any language produced from the union, intersection, and so on would be regular.
What if we have a regular grammar that ...
0
votes
1answer
24 views
Find a grammar for this language
Assume the language:
$$L=\left\{w\in\{0,1\}^*\,| \text{ w has odd length and 111 right in the middle}\right\}$$
This is my attempt for constructing a grammar $G$ for this language:
$$G: S \...
0
votes
1answer
21 views
Reusing variable in converting grammar to Chomsky Normal Form
I'm not sure if reusing variable is allowed in CNF.
For example, I have this grammar not in CNF. So I have to convert it to CNF.
...
0
votes
0answers
16 views
Merging nonterminals of a Context-Free Grammar?
I am reading through a paper on grammatical inference and stumbled upon the following:
Given positive example w, we first construct the tabular
representation T(w) and the primitive CFG G(T(w)), ...
1
vote
0answers
17 views
Generalization of formal grammars - production rules with more general functions?
Usually formal grammars have production rules in the format N=tNt where simple concatenation function is used for the expansion of the nonterminal. https://www....
-1
votes
0answers
19 views
$L_4 = \{x: \#_{1}(x) = 2 \cdot \#_{10}(x) \}$ Find CFG given hints [closed]
Attempt:
$S \to A_{00}SA_{11}$
$A_{00} \to 0, 0A_{00}, 0A_{10}$
$A_{01} \to A_{00}1, A_{00}A_{11}, A_{01}1, A_{00}1$
$A_{10} \to 1A_{10}, A_{10}0, 1A_{00}$
$A_{11} \to 1, 1A_{11}, 1A_{01}$
Not ...
0
votes
0answers
21 views
How to modify this CFG to use the conjunction (and) for two sentences?
I wrote the following CFG to parse sentences such as (tom ate pizza), (bill ate rice)...etc.in PROLOG.
s(s(NP,VP))-->np(NP),vp(VP).
vp(vp(VBD,NP))-->vbd(VBD),np(NP).
np(np(NN))-->nn(NN).
np(np(NNP))-...
1
vote
1answer
35 views
context free grammar for palindrome: $L_n = \{x \in \Sigma^* | x = ywz, w^R = w, |w| \geq n, |y| = |z| \}$
Let $L_{n} = \{x \in \Sigma^* | x = ywz, w^R = w, |w| \geq n, |y| = |z| \}$
Generate a cfg of $L_n$
For n = 1, 2, 3
Informally, x is in $L_n$ means
some palindrome of at least length n is a ...
1
vote
2answers
42 views
How to add decimals to formal grammar?
I have a formal language that describes digit production like
<digit> ::= 0|1|2|...|9
and I need to intruduce fraction to write decimals like ...
0
votes
0answers
23 views
Is the following language regarding P=NP/P!=NP decidable? [duplicate]
Let A = {w|w $\in$ {0,1}, such that
w=0 iff P=NP
w=1 iff P!=NP
Would the language itself be decidable?
3
votes
0answers
14 views
Base-k representations of polynomials: state of art [closed]
In chapter 4 of Jeffrey Shallit's A Second Course in Automata Theory the following problem is formulated as open:
Let $p(n)$ be a polynomial with rational coefficients such that $p(n) \in \mathbb{N}$ ...
-1
votes
0answers
24 views
Context-free grammar for all words of the form $a^{3i+1} b^{2j+1}$
How can I create a context-free grammar for the following language?
$$ L = \{a^{3i+1} b^{2j+1} \mid i, j \ge 0\}$$
0
votes
1answer
32 views
How to eliminate ambiguity of the follwing CFG?
Consider the following CFG:
$S\to AED | F \\
A \to Aa | a\\
B \to Bb | b\\
C \to Cc | c\\
D \to Dd | d\\
E \to bEc | bc\\
F \to aFd | BC$
The CFG produces $a^*bbb...ccc...d^*$ (equal number of b,...
0
votes
1answer
43 views
Proof that the grammar is LL(2)
I am given the following grammar:
$
S \rightarrow AabAba
\\
A \rightarrow a | \epsilon
$
and I have to prove it is LL(2).
I know what LL(k) means - one can choose a production based on k characters ...
1
vote
1answer
11 views
Why can't exhaustive search parsing stop after |w| + 1 derivations?
If my grammar does not have productions of the form $A\rightarrow\lambda$ and $A\rightarrow B$ for some variables $A$ and $B$ then I know that each step in the derivation must involve an increase in ...
2
votes
1answer
69 views
How to prove prove $L(G) = \{~w\in\{a,b\}^*~|~\#_aw= \#_bw\}$ for my CFG $G$?
For language $L = \{ x \in \{a,b\}^* \mid \#_a x = \#_b x \}$, I came up with the following CFG:
$$S \rightarrow aSbS \mid bSaS \mid \varepsilon.$$
It can be easily shown that it is correct (quick ...
0
votes
1answer
39 views
Context-Free Grammar from this language
I'm having difficulties with an exercise in a theoretical CS class.
The problem is:
let $L_{2}$ be a language defined as follows: after every "a" come atleast two "b" or after every "b" comes atleast ...
0
votes
0answers
60 views
Convert right linear grammar to left
Are there any (for example in literature) rules for converting right linear grammar to left? I found the algorithm from right to left, but not the opposite. Thanks for help
-1
votes
1answer
28 views
Convert grammar to Greibach form
The grammar is $S \rightarrow AA|a$$A \rightarrow SA|ab$The actual question is to find an NPDA accepting the language generated by this grammar but for that i firstly need to convert it into Greibach ...
1
vote
1answer
58 views
CFG - Ambiguous to Unambiguous
Given the ambiguous CFG :
S β 01S1|SS|Ο΅
I came up with the following CFG which I think is unambiguous:
S β 01X | 011X
X β 01X1 | Ο΅
Is my CFG unambiguous and does it represent the same language?
0
votes
1answer
54 views
How many parse trees are there of a given string?
Given a CFG, is there a systematic way to figuring out how many parse trees there are for a certain string?
For example, given the grammar:
...
1
vote
1answer
41 views
CFG for language of all palindromes whose number of 1s is divisible by 3
The question is the following:
Construct a CFG for $L_2 = \{w β {0, 1}^* \mid w = w^R\text{ and the number of 1βs in $w$ is divisible by 3}\}$.
I can construct a CFG for $\{w \in \{0,1\}^* \mid w =...
0
votes
1answer
35 views
What's wrong with this grammar
$L = \{ w : w \in \{a, b\}^* \land |w|_a = |w|_b\}$ where $|w|_a$ means number of $a$ in string $w$.
I came up with this grammar:
$S \rightarrow aSb \ |\ bSa \ | \ \epsilon .$
Can someone please ...
2
votes
0answers
22 views
Simple description of circularities in Knuth original attribute grammar paper
Knuth's original attribute grammar paper (title: Semantics of Context-Free Languages) introduced three types of circularity. More specifically section "Testing for circularity" page 134-5 figures 3.1-...
0
votes
0answers
13 views
How to create a context free grammar for the complement of the following language? [duplicate]
Let $L = \{xcx |x\in\{0,1\}^*\}$, the terminal symbols being $\{0,1,c\}$.
The complement would accept the following types of strings:
Strings with no c's, i.e. $\{0,1\}^*$
Strings with a single c, ...
0
votes
0answers
25 views
How do I create a regular grammar
I need to create a regular grammar $G$ for the following language: $L(G) = (L_1^* x L_2) \cup L_2$, where $L_1 = \{\mathrm{one}\}$ and $L_2 = \{\mathrm{two}\}$.
Can this be a correct regular grammar:
...
3
votes
1answer
55 views
Find a regular grammar that generates language $L$
I have a language $L$ = {$vabu$ | $v$,$u\in \{a,b\}^*$, $|vu|_a = 0$ $($mod $2)$$\}$
where $|vu|_a$ is number of $a$ in $vu$.
I came up with these rules:
$\sigma \rightarrow aa\sigma | ab\xi$
$\...
2
votes
3answers
42 views
Given an CFG determine if $\varepsilon \in L(G)$
Given a context free grammar how am I able to determine if $\varepsilon \in L(G)$ ?
The only way I thought of is to systematically check if I can derive the empty word from the given grammar. (...
1
vote
1answer
76 views
Is the problem of determining whether a CFG generates a string in the form 0*1* decidable?
Given a grammar $G$, is it decidable whether $G$ generates any string in the form $0^*1^*$? Why?
I think it's undecidable but can't find any undecidable problem to reduce it to.
1
vote
3answers
86 views
What is a non-ambiguous CFG for generating the set of natural numbers?
I'm trying to write a non-ambiguous context-free grammar that can generate the set of natural numbers, including the 0. My current solution is the following grammar:
$\mathcal{G}: S \rightarrow 0\ |\ ...
3
votes
1answer
71 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
25 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
31 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
59 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
79 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
46 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
47 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
48 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
57 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
24 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
20 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
83 views
0
votes
1answer
40 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
51 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
51 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
33 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
48 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
15 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 ...
