# 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)

210 questions
Filter by
Sorted by
Tagged with
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 ...
57 views

• 331
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 ...
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 ...
• 20.2k
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$, ...
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 ...
• 17
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, ...
• 1,825
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 ...
• 3,906
1 vote
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. ...
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 ...
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 ...
36 views

• 835
76 views

• 11
1 vote
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$...
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 ...
• 335
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 ...
• 3,546
1k views

• 47.2k
1 vote
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 ...
• 47.2k
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 ...
• 4,922
1 vote
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 ...
• 1,293
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 ...
• 103
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 ...
• 3,413
1 vote
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 ...
• 47.2k
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$ ...
• 121
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^...