Stack Exchange Network

Stack Exchange network consists of 175 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 tagged [formal-grammar]

In formal language theory, a grammar (when the context is not given, often called a formal grammar for clarity) is a set of production rules for strings in a formal language. A formal grammar is a set of rules for rewriting strings, along with a "start symbol" from which rewriting starts. Therefore, a grammar is usually thought of as a language generator. (Def: http://en.m.wikipedia.org/wiki/Formal_grammar)

3
votes
1answer
58 views

Codification of a formal language in set theory.

Starting with an arbitrary class of sets $\Gamma$, can you generate a free semigroup $\Gamma^*$ over $\Gamma$ with the group operation of concatenation ($\frown$)? The goal here is to codify a formal ...
1
vote
0answers
32 views

How to prove that models of indirect and direct RAM machines are equivalent?

as in the title, I am looking for a formal proof how to show that models of indirect and direct RAM (random-access) machines are equivalent. I would really appreciate your help.
1
vote
1answer
30 views

Language contex-free

$$L=\{a^kb^nc^md^t\mid n+m=2(k+t)\}.$$ So I am trying to figure out if this language is CFL. So trying to prove that it is not CFL with the pumping lemma, I am not getting anywhere (using the word $a^...
0
votes
1answer
31 views

Is $L_4$ a CFL?

Consider the following language: $$L_4 = \{a^ib^jc^kd^l : i,j,k,l \ge0 \wedge i=1 \Rightarrow j=k=l\}.$$ Prove or disprove: $L_4$ is a context-free language. To me, it looks like $L_4$ can be ...
0
votes
1answer
33 views

Language contex-free or not?

I was wondering whether this language is context-free or not? It's $L = \{ AB ~|~ |A| = |B| \text{ and } A \neq B \}$ . The alphabet is $\{ a, b \}$. In my textbook it's written that it is ...
1
vote
0answers
116 views

Prove that Dyck language is subset of grammar

last two days I am trying to prove, that Dyck language $L$ over the alphabet $\{[, ]\}$ is a subset of the language $L(G)$ generated by the grammar with rules $\{S \rightarrow [S]S | \epsilon \}$. ...
1
vote
0answers
31 views

Context Free grammar to Chomsky Normal Form

So I got: $ S \rightarrow XY|a $ $ X \rightarrow XYb|XS|\varepsilon$ $ Y \rightarrow SY|cX|XX|a$ So I want to solve this step by step ( first seperate, avoid length $\geq$ 2, avoid $\varepsilon$, ...
0
votes
1answer
148 views

Binary prime numbers: grammar

I want to write a grammar which produces binary prime numbers. But I can't find any patterns this grammar can be made of. Like this: ...
1
vote
0answers
35 views

Is there a non-Abelian algebra such that sequences can be 'reconstructed' given constraints?

Disclaimer: I'm a software engineer trying to use mathematics to solve a problem. I only have a shallow understanding of (abstract) algebra. My terminology will probably be wrong. Please be gentle. I'...
-1
votes
1answer
29 views

Reported speech [closed]

I want to know the following sentence Wrong : “He said that all students should focus during the lesson so they would not get hurt.” Right : “He said that all students should focus during the ...
0
votes
0answers
40 views

“Reasonable” exponential-time parsing expression grammar (PEG)

Parsing Expression Grammars (PEG) are basically a formalization of top-down recursive-descent parsers. A naive implementation of PEG has worst-case exponential run-time (i.e. implemented as a top-...
0
votes
1answer
28 views

What type of grammar is this, and what type of language does it generate?

Notation seems to vary a bit on here, so for this question: $N$ is the set of nonterminals $\{S, A\}$, $T$ is the set of terminals $\{a, b, c\}$ $P$ is the set of productions $u \rightarrow v$. I ...
1
vote
0answers
41 views

Equivalent grammar

Consider the grammar $G=(\{S,A,B\},\{0,1\},P,S)$, where $P$ consists: $S\to AB$ $A\to BSB$ $A\to BB$ $B\to 0A1$ $B\to 0$ $A\to 1$ $B\to e$ Find equivalent grammar for which S does not appear ...
2
votes
1answer
36 views

Construct a grammar that generates the language $L = \{ a^x b^{x-y} c^y \mid x > y > 0 \text{ and } (x + y) \text{ is even }\}$

I have the following problem: Construct a grammar that only generates the strings that belong to the language $L$ where: $$ L = \{ a^x b^{x-y} c^y \mid x > y > 0 \text{ and }(x + y) \text{ ...
0
votes
0answers
26 views

How to express a plural of the cardinalities of sets?

I express variables $x_1, x_2, \ldots$ as "$x_i$'s". Similarly, when I want to express sets $\mathcal{S}_1, \mathcal{S},2, \ldots$, I also use $\mathcal{S}_i$'s. However, when I want to express the ...
0
votes
0answers
25 views

A method of expressing constraints mathematically and formally.

There is a statement, "For any natural number $x$ not larger than $N$, $f(x,y)$ is not greater than $c_x$ for all $y$ in $\mathcal{A}_x$." I want to put this statement into the optimization problem ...
-1
votes
1answer
26 views

How to create a string grammar from {(,)}* set?

How to create a grammar that would imitate all the strings from the from the set {(,)}*, and in which (lines) all the parantheses would hava a correct place? I just do not know how to start, I am a ...
1
vote
0answers
25 views

What grammar domain is this kind of grammar?

I am new to the concepts of grammars, but I need to figure out what grammar domain I am working in. I know it is not a context-free grammar (by reading the answers to What does “context-free” mean in ...
1
vote
1answer
38 views

Equations on the free monoid??

While studying a bit of Joachim Lambek's calculus and some other applications of formal languages to the study of the structure of human language, I have come accross a reference to what authors like ...
0
votes
1answer
15 views

Proving a Formal Grammar Parses a String.

In summary, I am interested to know (at a high level) what a proof would look like, and what I would need to do in developing a grammar, to "prove" that the grammar matches some patterns I have in ...
0
votes
1answer
28 views

Converting regular grammar to a regular expression

I have a regular grammar that looks like: ${S \rightarrow aS, S \rightarrow bB, A\rightarrow \Lambda, A\rightarrow aS, A\rightarrow bB, B\rightarrow aA, B\rightarrow bB, B\rightarrow \Lambda}$ And I ...
1
vote
1answer
54 views

Write grammar for language $L=\bigl\{ba^{2^n}b \mid n\ge 1\bigr\}$

Write grammar for language $L=\{ba^{2^n}b | n\ge 1\}$. It can be grammar of any type without any restriction on rules look. My best attempt is: \begin{aligned} S &\to RLM \\ M &\to AM | A \\ ...
0
votes
0answers
38 views

A dumb question regarding graph grammars and Feynman diagrams

Good day to all!! Please consider the following Powerpoint by Matilde Marcolli: http://www.its.caltech.edu/~matilde/GraphGrammarsLing.pdf I require your attention to be fixed on the antepenultimate ...
2
votes
1answer
494 views

Given a grammar study its type and the language it generates

I have to find out if the grammar $G=(\{A,B\},\{x,y\},A)$, where the productions of $P$ are given by $$\begin{array}{ccc}A&\rightarrow &x\:A/y\:B\\B&\rightarrow &x\:B/x\end{array}$$ is ...
1
vote
1answer
41 views

Is this finite state machine correct?

I have to build a f.s.m. for the language $((00)(0+1)^*)+((0+1)^*(110))$ is this correct?
0
votes
0answers
66 views

Create a grammar for the language $L =\{a^n b^{n/2} c^n\mid n\equiv 0\pmod{2}\}$

I am interested in a grammar for the language L which defined as follows: $$ L=\left\{ { a }^{ n }{ b }^{ n/2 }{ c }^{ n }\mid n\bmod2=0,\quad n\in\mathbb N \right\} $$ My idea is to substitute n ...
0
votes
1answer
36 views

Given language, say if it is regular, context-free and proove it.

I have the following language: $L = \{a^{2m + k}b^{3n+\ell}c^{m+n} \mid \ell\leq3 \space\text{and}\space k\gt2\space\text{and}\space m,n \in\mathbb{N}\}$ Is it regular? Is it context-free? What I ...
1
vote
0answers
27 views

Minimized single-string grammar size approximation.

Let $|\Sigma_s| = m$ alphabet and $|s| = n$ be the size of our string. Consider a minimized grammar $g$ expanding to $s$, with start symbol $S \in \Sigma_g$. Then what's the maximum length $n$ such ...
0
votes
1answer
72 views

Context Free Grammar - Do we consider epsilon when looking for generating symbols?

I'm learning about Context Free Grammars and I've come across the algoritm of removing non-generating symbols. I've checked a few sources but sadly was unable to find an answer. At first we consider ...
2
votes
1answer
55 views

Sampling uniformly from the language generated by a grammar

Suppose I have the following formal grammar: $$ S \rightarrow \varepsilon + a S + b S + c S d S $$ where $S$ is a nonterminal symbol and $a$, $b$, $c$, $d$ are terminal symbols. How can I sample ...
1
vote
0answers
54 views

Context Free Grammar from Language

I'm given the language M = {c^m d^n | 2m > n > m} and need to find a context free grammar for it What I came up with are the 2 production rules: S -> ccTddd T -> cTdd | ϵ This however doesn't take ...
0
votes
1answer
39 views

Decoding Equivalence Relations

Working on a problem set in which I need to evaluate a set of relations for transitiveness, symmetry, and reflexiveness. Intuitive relations seem graspable but more difficult relations just seem ...
0
votes
1answer
85 views

Do these grammars produce the same language?

I was solving a problem on CFG and saw this "simplification" in two of the rules. I believe these two grammars produce the same language, however I was not able to prove it. Grammar 1 : S -> A|B A -> ...
5
votes
0answers
88 views

A group action associated with a smallest grammar algorithm. Ways to reduce size?

See these two posts for a background: Smallest grammar algorithm recursion Smallest grammar algorithm group action Here is some output of code I've written in python. Ask if you want to run it. ...
1
vote
1answer
60 views

Given a finite set of group generators (via a group action on a finite set of objects), can we enumerate the group easily?

I have a clearly finite set of objects $S$ (single-string grammars of a strings $s$ over alphabet $\Sigma$, and a set of generators that generate what I call the smallest grammar algorithm group, $G$. ...
0
votes
1answer
36 views

A smallest grammar algorithm can recurse by decomposing into terminals, then repeating with increased alphabet.

Please scan the article on the smallest grammar problem. It is a simply-stated, major open problem because it directly relates to $\text{P vs NP}$ if an answer in either direction can be given. Let $...
0
votes
0answers
23 views

Finding a context-sensitive grammar for L [duplicate]

I need help for finding a context-sensitive grammar for the following language: $$ L = \left\{ ww \left| w \in \left\{a, b\right\}^* \right. \right\} $$ Would that be a correct context-sensitive ...
0
votes
1answer
376 views

Given G a phrase structure grammar, what is the language generated by G?

Given $G$, a phrase-structure grammar. Let $G = (V, T, S, P)$, where $V = \{a, b, A, B, S\}$, $T = \{a, b\}$, $S$ is the start symbol, $P = \{S \rightarrow ABb, A \rightarrow BB, Bb \rightarrow aA, B \...
1
vote
0answers
104 views

What is the FIRST and FOLLOW sets for this grammar…

With the definitions of FIRST being the set of terminal symbols that begin strings derived from α, and FOLLOW being: FOLLOW(A) = { a | S ⇒* αAaβ } What are the ...
0
votes
1answer
59 views

What grammar accepts this language?

When I have this language, what grammar would be accepted? $$\{w|w∈\{a,b\}^∗ \space\text{and}\space w=w^R\}$$ $S→ε$ $S→aB$ $B→bA$ $B→b$ $A→aB$ This would be my answer so far or am I wrong? I'm ...
0
votes
1answer
29 views

What is the language of the following CFG? [closed]

The CFG has the following productions where S is the start symbol, S and Y are non-terminals and a and b are terminals. S → bb ∣ SY Y → bYa | ba
2
votes
1answer
46 views

Quick question about grammars

I'm trying to discern whether or not I am answering this question correctly. If someone could shine some light on this, that would be greatly appreciated. So let's state for instance that we have the ...
0
votes
1answer
136 views

Confirming an Answer for Phrase Structure Grammar

I just want to confirm that I have a valid and good understanding of Phrase Grammar Structures by working one of the problems in the presence of you fellow mathematicians. Let's assume the following:...
0
votes
1answer
469 views

Having some problems with Phrase Structure Grammar

I am having some problems with Phrase Structure Grammar (formula being let G = (V, T, S, P) where V is a finite vocabulary, T is a subset of V, and S is a start symbol from V, and P are productions (...
0
votes
1answer
202 views

Convert this CFG to Chomsky normal form.

S -> uvSS | u | v | $\epsilon$ The Chomsky normal form of a context-free grammar is such that the grammar is in the form: A -> BC A -> a S -> $\epsilon$ Now, to start converting, I set the rule $...
0
votes
1answer
44 views

This is a ll(1) of logic propositions?

I have this is grammar : F = F and F F = F or F F = F => F F = F <=> F F = not F F = (F) D = a but this grammar has a ambiguity , i'm Stripped a ...
0
votes
1answer
585 views

The context free grammar for language $L = \{a^nb^mc^k \mid k = |n - m|, n≥0,m≥0,k≥0\}$ is

The context free grammar for language $L = \{a^nb^mc^k \mid k = |n - m|, n≥0,m≥0,k≥0\}$ is: $S→S_1S_3, S_1→aS_1c |S_2|λ, S_2→aS_2b|λ, S_3→aS_3b|S_4| λ, S_4→bS_4c|λ$ $S→S_1S_3, S_1→aS_1S_2c |λ, S_2→...
1
vote
0answers
81 views

formal grammar from automaton

Given this automaton $M=(Q,δ,q0,F)$ over alphabet Σ={a,p}Σ={a,p}: Find a regular grammar $G=( N,Σ,P,S)$ s.t. T(M)=L(G) I found this grammar and I would know if is correct: G=( N,Σ,P,S) where: N=Q ...
0
votes
1answer
620 views

Is there any language that $\bar L^*= (\bar L)^*$?

Can we answer to this question or no, this is unknown? Is there any language that $\bar L^*= (\bar L)^*$?
0
votes
1answer
36 views

Find a Context-Free Grammar for this Context-Free Language

$$ L = \{w_1w_2 : w_1, w_2\, \in \, \{a,b\}^*, w_1 \ne w_2\} $$ So far I have produced this grammar which will produce a string of odd length which follows that $w_1$ and $w_2$ wouldn't be equal. $$ S ...