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)

Filter by
Sorted by
Tagged with
0 votes
0 answers
16 views

Construct the grammar that generates the given languange

Find a grammar that generates this language : L = { w : |w| mod 3 >= |w| mod 2 } over the alphabet sigma = {a} I tried and got the abstract logic . Length where mod 3 < mod 2 is length should be ...
RAGUL KARTHICK's user avatar
-1 votes
1 answer
57 views

What is the language of the given grammar?

The given grammar goes as follows: $$S → aSa \mid B \mid \epsilon \\ Ba → bbBaa \\ aB → aaBbb \\ B → \epsilon$$ I derivated it and reached this language: $$L(G) = \{\epsilon, a^na^n, ab^2a^2, ab^4a^3, ...
Farbod Mirkazemi's user avatar
0 votes
2 answers
45 views

Exact meaning of terms in First-Order Logic

I have recently studied first-order logic, but I am confused on a very basic idea: Terms. Is the term the value inputed in $f(x)$ for $f(t_1....t_n)$, for example, it is $1$ in $f(1)$? Or is it, for ...
Zeyad's user avatar
  • 1
0 votes
0 answers
64 views

CFG for $L = \{w_1w_2 \cdots w_{2n} \mid n > 0, w_i \in \{a, b\}, 1 \leq i \leq 2n, w_j = b, w_{n + j} = a \ \exists j, 1 \leq j \leq n\}$

I think this is somehow related to the language describing all strings not of the form $ww, w \in \{a, b\}^*$, but I am still not quite sure how. Of course, I have done some thinking and it is evident ...
codeing_monkey's user avatar
1 vote
1 answer
47 views

Suppose we have unambiguous context-free language, how can we calculate the number of words that can be represented by $n$ terminals?

I am new to formal language theory, apology if this question seems obvious. Here are some definitions from formal language theory: Definition. Let $\mathcal{V}$ be a set of variables (usually denoted ...
ghc1997's user avatar
  • 1,299
0 votes
0 answers
58 views

How to construct the smallest set of all algebraic expressions?

I am a high school math teacher and I have a little side project that has been going on since some time: build a taxonomy of mathematical expressions. Specifically, let's define a set of symbols $S$ ...
marco trevi's user avatar
  • 3,292
0 votes
0 answers
33 views

regex for exactly n possible values which are unique

I want to write a regular expression in my python code, but I think this is more of a mathematical challenge. So my requirement is, suppose I want to create $3$ unique coupon codes, I can write a ...
zegulas's user avatar
  • 101
0 votes
0 answers
28 views

an unclear definition about the types of phrase-structure grammars

I am reading the book "Discrete Mathematics and Its Applications" written by Kenneth Rosen. I've encountered some troubles. When it introduced the type-2 of phrase-structure grammar to me, ...
FallInClouds's user avatar
1 vote
0 answers
33 views

How to create grammar that generates language $L = \{ w \in \{a, b, c\}^* | \#_a(w) = \#_b(w) \cdot \#_c(w) \}$

I want to know how to create CSG (context sensitive grammar) that generates this language $L$. My idea is that every time when adding another b, add as many a's as the word contains c's and vice versa ...
junk fod's user avatar
-1 votes
1 answer
59 views

How might we formally define the concatenation of two strings?

Below we offer some definitions of string. How would you mathematically define the concatenation of strings? The $\mathtt{HELLO\ WORLD}$ Example $“\mathtt{HELLO}” + “\mathtt{\ }” + \mathtt{WORLD}” = ...
Toothpick Anemone's user avatar
1 vote
1 answer
76 views

Are there common "phrases" in complex Mathematical notation? [closed]

More precisely, are there complex mathematical-notation-patterns that convey more meaning to somebody who's seen and understood them before, than they do to somebody who's just seen them? (Even if the ...
Connor's user avatar
  • 647
0 votes
1 answer
70 views

Is the set of languages that can be recognized by combinational logic smaller than those recognized by regular expressions?

In the Wikipedia article on Automata theory there is a diagram that suggests that combinational logic recognizes a proper subset of the languages that a regular expression recognizes. Is this in fact ...
Shadow43375's user avatar
0 votes
1 answer
48 views

Does a formal language require a grammar?

Given some alphabet $\Sigma$ we can define some language $L$ as a subset of the set of all possible words $\Sigma^*$ that use the symbols found in the alphabet. It seems that there are two ways of ...
Shadow43375's user avatar
0 votes
0 answers
46 views

Which language will be generated by the following grammar?

So i have $$ G = (V,\sum, S, P) $$ while $$ V = {S, A, B} $$ $$ \sum = {a,b,c}$$ and for P: $$ P:= \begin{cases} S \rightarrow & cA\ | \ bB, \\ A \rightarrow & c, \\ B \...
JohnGam's user avatar
  • 331
0 votes
0 answers
34 views

How to derive a language when there is an unreachable non-terminal symbol?

I have this formally defined grammar : $$\begin{array}{rl}G=\langle&\{S,B,C\},\\&\{a,b,c\},\\&\{S\to CSB\mid CSa\mid a,B\to b\mid\epsilon,C\to c\},\\&S\rangle\end{array}$$ I know how ...
Sam Kiloz's user avatar
0 votes
0 answers
28 views

Formal grammars of these two languages of hereditarily finite sets.

This is a follow-up to my previous question, here: How to formally define this language of hereditarily finite sets?. Let our alphabet be composed of the left brace, right brace, the comma, and the ...
user107952's user avatar
  • 20.2k
0 votes
1 answer
92 views

Prove a subset of a regular language is regular, context-free but not regular or not context free [closed]

I've been tasked with solving this problem, but I'm not sure where to begin: Let $L$ be a context-free language. $L'$ contains all the words that belong to $L$ which can't be defined as $z=uvwxy$, ...
Eatay Mizrachi's user avatar
0 votes
0 answers
39 views

How to build a proof using structural induction? [duplicate]

I am requested to build a proof for the following I am requested to prove the following statement, however I have no idea on how to begin... Does any of you know how can I do such induction on the ...
lucasbbs's user avatar
0 votes
1 answer
161 views

Pumping lemma: if you pump to $uv^0wx^0y$, wouldn't $|vx| \ngeq 1$?

For pumping lemma for CFLs, for strings $s$ in $L$, they follow the form $s = uvwxy$ and $|vwx| \leq n$, $|vx| \geq 1$, and $uv^iwx^iy \in L$ for $i \geq 0$. If I want to prove a language is not CFL, ...
gator's user avatar
  • 1,825
0 votes
1 answer
79 views

the Chomsky hierarchy vs. classical complexity classes

What are the obvious (and less obvious) relationships between classical complexity classes like P,NP,PSPACE,EXP and the Chomsky hierarchy of grammars for the language $L$ in question, context-free and ...
user122424's user avatar
  • 3,906
1 vote
1 answer
104 views

How to create a grammar with a multiplication, to generate $a^ib^jc^k$ with $k=i \cdot j$?

The exercise I found has this language $L=\{a^ib^jc^k: k=i \cdot j\}$ on the alphabet $\Sigma = \{a, b, c\}$, and although it has nothing to do with creation of grammars, I decided to give it a try. ...
Alexandre Tourinho's user avatar
0 votes
1 answer
147 views

Provide a grammar to generate strings that are only made of 1’s, where A={0,1}

My solution so far is as follow: S -> 1S | 1 Is it necessary to include lambda in this grammar? Edit: To further elaborate, my logic is that since lambda is not 1 it does not belong in the grammar ...
bugasker4's user avatar
0 votes
1 answer
44 views

Finding the equivalent regex for a formal grammar

We have the following formal grammar: $a, b$ are terminal symbols. $S, A, B$ are non-terminal symbols. $S$ is the startsymbol. Thinking in terms of a nondeterministic finite automata $q0$ indicates ...
curiousMind_85's user avatar
2 votes
0 answers
36 views

constructing grammar for 1*0*1(1+0)*

I want to construct a grammar for the following regular expression: $1^*0^*1(1+0)^*$. I did it the following way: $S \rightarrow AB1C$ $A \rightarrow 1A | \epsilon$ $B \rightarrow 0B | \epsilon$ $C \...
Papa's user avatar
  • 483
0 votes
1 answer
220 views

Combination of 2 context free grammars

I am required to show that the language $L$ is context-free where $$L = \{q_1q_2 \dotsm q_nt_1t_2 \dotsm t_n \mid q_i \in Q, t_i \in T, n \geq 0 \}$$ where $Q$ and $T$ are context-free languages. I ...
Turtle's user avatar
  • 36
-1 votes
1 answer
114 views

Is $a^n b^n$ context free even if we take strings instead of characters?

Let a and b be 2 strings . Does the set {$a^nb^n$ , $n\geq0$} still form a context free language? Intuitively, I feel that should be the case since in this case I'm just storing strings instead of ...
Turtle's user avatar
  • 36
1 vote
1 answer
21 views

Does additive quasigroup generated by arbitrary subset $K$ of natural numbers contain each sufficiently big $\gcd (K)$ multiplication?

I'm wondering if for every set of positive integers $\{a_0, .., a_{n-1}\}\subset\mathbb{N}_+$ with $g:=\gcd\{a_i:i<n\}$ there is $M_0$ such, that for each $M\geq M_0$ there exists $\{b_i:i<n\}\...
Przemek's user avatar
  • 835
2 votes
1 answer
76 views

Formalization of Lemma for proof of AM-GM inequality

The question is not about how to prove the lemma (I proved it by induction) but I wanted to understand the correct formalization of the lemma: Lemma used to prove AM-GM inequality: If $ a_1,a_2,...,...
hazelnut_116's user avatar
  • 1,635
0 votes
0 answers
22 views

What specific properties of CFGs & CSGs do we lose, when we redefine the starting symbol to be either terminal or non-terminal?

Both CFG(Context-Free Grammar) & CSG(Context-Sensitive Grammar) are defined as a 4-tuple $(V,\Sigma,R,S)$, with $S\in V$. That is, in both cases $S$(the starting symbol) is a non-terminal symbol, ...
Sofviic's user avatar
  • 33
1 vote
1 answer
68 views

Can we find grammar for every CFL without $ε $ with these productions

So we have a CFL that doesn't have $ε$ and I have to prove that we can find a grammar for that language with all productions like this $A->BCD$ or $A->a$. I'm thinking about dividing $A->BCD$ ...
Nice guy's user avatar
2 votes
2 answers
491 views

How to prove that my CFG grammar generates $L_1$

I had to come up with a CFG for language $L_1=$$(a+b)$*$-L$ where $L =$ {$a^nb^n: n∈N$} . So my CFG has these $S\to a\mid b\mid bS\mid Sa\mid aSb\mid bSb\mid aSa$ . And I am pretty sure that it ...
Nice guy's user avatar
0 votes
1 answer
584 views

How to prove that L* is context free?

Let's say we have a language of form: $L =$ {$a^nb^n: n∈N$}. I want to prove that $L^*$ is a context-free language. How do I approach this problem? I know that $L$ generates CFG (context-free grammar) ...
jasiu's user avatar
  • 49
1 vote
0 answers
39 views

Uniqueness quantification for inverse elements, for all elements of a group / uniqueness quantification for identity element, is this correct?

Given a group consisting of the following : $\mathbb{G} = (\mathrm{G}, +)$ where : $\mathrm{G}$ is the underlying set of the group algebraic structure $+$ is an internal binary operation which ...
Guilhem Escudéro's user avatar
1 vote
0 answers
21 views

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 + ...
WarChild's user avatar
1 vote
0 answers
15 views

Can an indexed grammar exclude a prefix from a postfix?

The problem is to define or prove the impossibility of defining an indexed grammar for the set of strings $A q B$ such that $A$ is at least one symbol and does not contain $q$ $B$ does not contain $q$...
Axel Svensson's user avatar
0 votes
1 answer
107 views

Give an expression that describe the language generated by this grammar

the grammar: I tried to breakdown the problem but i am not sure what the end result expression could be. I have to give an expression and try to describe this grammar. Here's what i did for now : I ...
codetime's user avatar
  • 335
0 votes
1 answer
29 views

Does every restriction on word formation constitute a formal grammar?

Consider an alphabet $\Sigma$ from which I can generate words, which are just concatenations of symbols from the set $\Sigma$. I then define some "rule" that indicates whether or not a word ...
aghostinthefigures's user avatar
0 votes
1 answer
1k views

Context free grammar for palindrome over ALL terminals?

I've found various examples of context-free grammars for palindromes but they all seem to hardcode the rules to be of the form "terminal Statement (same) terminal" For example, if $T \...
Prithvi Boinpally's user avatar
0 votes
0 answers
85 views

Converting a regular expression to a grammar and regular grammar

I tried looking around for help before posting this but either the question did not match mine or I was not able to understand the answer posted due to my lack of knowledge. I am working on a lab and ...
AFC's user avatar
  • 383
2 votes
0 answers
189 views

What is the connection between the language (of some formal grammar) and algebra on the words of this language?

Formal language is the set of words that are generated from production rules. There are 2 kind of operations on such language: application of production rules to generate new (grammatically valid) ...
TomR's user avatar
  • 1,293
1 vote
1 answer
592 views

What are the relations and differences between formal systems, rewriting systems, formal grammars and automata?

I learned from Herre & Schroeder-Heister's "Formal Languages and Systems" that A formal system is based on a formal language $L$, endowing it with a consequence operation $C: 2^L\to 2^...
Tim's user avatar
  • 47.2k
1 vote
0 answers
30 views

How is any algorithm expressed respectively by a grammar, a Turing machine and last but not least a rule-based system?

In Herre & Schroeder-Heister's "Formal Languages and Systems", on p7, Like grammars, rule-based systems (e.g. deductive systems in logic) are as powerful as Turing machines, i.e. they ...
Tim's user avatar
  • 47.2k
0 votes
1 answer
458 views

Define "first-order language" without using it

I am struggling to define "first-order language." In principle, a first-order language is any language produced by a "first-order grammar," but there doesn't seem to be any way to ...
R. Burton's user avatar
  • 4,922
1 vote
0 answers
43 views

Is the set of all grammatically correct words a lattice and is there grammar for which this set is not lattice?

Let G be a formal grammar of any Chomsky type (as defined by the production rules) and let the production rules establish the order among words of this grammar: words a and b are a<=b if a can be ...
TomR's user avatar
  • 1,293
0 votes
1 answer
83 views

Context free grammar for language $\{ \{a,b\}^*$: where the number of $a$'s is unequal to the number of $b$'s$\}$

I've seen many solutions for when the number of $a$'s and $b$'s ARE equal but how should the grammar be for the time when the numbers are unequal? So far I have this but it can't produce many things ...
Nitwit's user avatar
  • 103
0 votes
0 answers
19 views

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 ...
Danny_Kim's user avatar
  • 3,413
1 vote
0 answers
19 views

Does formal language theory have concepts corresponding to dependency grammars?

If I am correct, phrase structure grammars in linguistics are the grammars for recursively enumerable languages. Does formal language theory have concepts corresponding to dependency grammars, the ...
Tim's user avatar
  • 47.2k
0 votes
1 answer
43 views

Converting linear grammar to normal form

I have a grammar that has the following productions: $S\to aSbb$, $S\to aSa$ and $S\to c$ I am supposed to convert this grammar to normal form where the productions have to be as follows: $A\to aB$ ...
Samsam22's user avatar
  • 121
0 votes
1 answer
68 views

Proof for pumping lemma for new kind of CFL

I have a context-free grammar $(V,\Sigma,R,S)$ that is defined by the condition that every production in $R$ has to be on one of the following two forms: $A\to uBv$ where $A,B\in V$ and $u,v\in\Sigma^...
Samsam22's user avatar
  • 121
0 votes
1 answer
190 views

Are axioms in math equivalent to production rules in unrestricted grammars?

In other words, the Curry–Howard correspondence is the observation that two families of seemingly unrelated formalisms—namely, the proof systems on one hand, and the models of computation on the other—...
Jesus is Lord's user avatar

1
2 3 4 5