Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

Why I can't parse factorial? [closed]

Given that I have a simplified Bison BNF grammar: ...
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 ...