Mathematics Stack Exchange
Mathematics 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)

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. Reference: Wikipedia.

The rules describe how to form strings from the language's alphabet that are valid according to the language's syntax. A grammar does not describe the meaning of the strings or what can be done with them in whatever context—only their form.

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.

211 questions
3
votes
1 answer

Context free grammar and regular expressions

Consider a grammar $G = (V, \Sigma, R, S)$ where $V = \{S\}$, $\Sigma =\{A, B\}$ and $R$ has two production rules, namely $S \to S^+ AS $ and $S \to B$. Is $G$ context-free? The $^+$ symbol is Kleene plus. The definition of a context-free grammar…
user231541
  • 33
2
votes
1 answer

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 following phrase-structure grammar: Which…
Linuxn00b
  • 29
1
vote
0 answers

Make formal grammar for the language

I have homework at my university and there is a task which I don't know how to do. I have a language and I should make a grammar which matches the language. Here's the language $L=\{a^pb^qc^r \mid p + q > r; p, q, r >=0\}$ I know how to do the…
WarChild
  • 11
0
votes
1 answer

Predictability of a grammar

I've encountered this in a book: The language $ \{ a^n0b^n \mid n ≥ 1\} ∪ \{a^n1b^{2n} \mid n ≥ 1\}$has no predictive grammar. (A predictable grammar is that in which no two rules of production for a same symbol have the same starting symbol) I…
carllacan
  • 391
0
votes
0 answers

In inline equations, should I use parentheses to represent the sum of two or more variables?

In inline equations, should I use parentheses to represent the sum of two or more variables? Let me give an example. Suppose that there are $5$ nodes, denoted by $n_1, n_2, \ldots, n_5$, and each node has its own reward value according to its given…
Danny_Kim
  • 3,423
0
votes
2 answers

Finding context-sensitive grammar for a given language

I was wondering, in my other topic, how to find grammar for: $\left\{ a^n b^n c^n: n\ge 1 \right\}$ when I found this. Context-sensitive grammars is completely new topic for me and I don't understand few things. Firstly: why is it OK? I think I get…
xan
  • 2,053
0
votes
0 answers

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 cardinalities of the sets, how to…
Danny_Kim
  • 3,423
0
votes
3 answers

The set of words in {a,b,c}∗ that do not contain the substring bc.

I couldn't write nfa or dfa for the language above. Please, help me!
linguist
  • 1
0
votes
0 answers

Finding a context-sensitive grammar for L

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 grammar? S -> ε | AUAV | BUBV (1) U -> AUC | BUD …
askleg
  • 11
  • 1
0
votes
1 answer

Estimate size of L-system string

I am writing a program to work with L-systems (Lindenmayer Systems) and I need to know how much memory to allocate for the strings, but my problem is clearly a math problem, not a programming one. Here's my situation: I have an arbitrary starting…
Void Star
  • 2,555
0
votes
1 answer

Construct a Grammar for a language that includes mod

I am trying to construct a regular grammar for the following language: $$L = \{ w \ | \ (na(w) - nb(w))\mod3!= 1 \}.$$ I'm struggling to understand what it is this language produces, and thus struggling to create a grammar for it. We want a…
Talen Kylon
  • 563
-1
votes
1 answer

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 bit newbie in grammars :/
M.Mass
  • 2,672