<p>I wonder, whether there is any strategy/ies for grammar derivation of a formal language. I'd be thankful, if you give me some hints, tips on how should one "think" trying to find a grammar. I'm interested in all types of grammar, but mostly in Typ-3 (regular grammar and it's languages). </p>

<p>For example, I need to find a grammar for $a^{n}b^{n}c^{n}$ language. And my questions are:
- can we decide at first sight, which grammar we should use? If yes, 
- how should we find the right amount of variables? </p>

<p>I know, that this language can be generated by Typ1-Grammar (context-sensitive). And I have it's grammar (or one of possible grammars). But I would like to learn how to be able to find it by myself. I'll be thankful to you if you can help me.. </p>

CC BY-SA 3.0
2011-10-26T16:03:32.487Z
I'm not sure I understand. You are given a language (in what form) and wish to compute a grammar for it ?
Suresh Venkat
CC BY-SA 3.0
2011-10-26T17:54:49.973Z
Perhaps you could give a bit more information/context. What classes of grammars/languages are you interested in (regular, context-free, ...)? Is there a specific language you're interested in, or otherwise what is your motivation?
Max
CC BY-SA 3.0
2011-10-27T08:50:32.637Z
@Suresh Venkat, 
right, I'm given a some language, which is described in general form (as a function, f.e.). And I need to write a grammar for this language.
Lissa
CC BY-SA 3.0
2011-10-27T08:53:45.160Z
@Max, 
I'm interested in all types of grammar, but mostly in Typ-3 (regular grammar and it's languages). 

For example, I need to find a grammar for $a^{n}b^{n}c^{n}$ language. And my questions are: 

- can we decide at first sight, which grammar we should use? If yes, 
- how should we find the right amount of variables?

I know, that this language can be generated by Typ1-Grammar (context-sensitive). And I have it's grammar. But want to learn how to be able to find it by myself.

So.. is there any strategy for grammar derivation? Maybe something to every types of them or at least for regular.
Lissa
CC BY-SA 3.0
2011-10-27T18:24:19.820Z
I originally thought the problem was to *automatically* determine a grammar from a language spec. It now sounds more like you want help in *thinking* up a grammar from a language spec. This latter question I think is a little out of scope for this site, since it really pertains to basic tools in automata theory, not research-level questions in the area.
Suresh Venkat
CC BY-SA 3.0
2013-10-27T01:51:14.197Z
@SureshVenkat , what if the question was "automatically" determine a grammar from a language ? what would be the answer ? Or in another words for example given a regular expression (as in PCRE) how to determine which grammar to validate the strings in that language ?
sashank
<fl.formal-languages><automata-theory>
Strategy for grammar derivation of a formal language
Lissa
# Strategy for grammar derivation of a formal language

(Asked by: username_0 on 2011-10-26)

I wonder, whether there is any strategy/ies for grammar derivation of a formal language. I'd be thankful, if you give me some hints, tips on how should one "think" trying to find a grammar. I'm interested in all types of grammar, but mostly in Typ-3 (regular grammar and it's languages).

For example, I need to find a grammar for $a^{n}b^{n}c^{n}$ language. And my questions are:
- can we decide at first sight, which grammar we should use? If yes,
- how should we find the right amount of variables?

I know, that this language can be generated by Typ1-Grammar (context-sensitive). And I have it's grammar (or one of possible grammars). But I would like to learn how to be able to find it by myself. I'll be thankful to you if you can help me..

**Tags:** fl.formal-languages, automata-theory

> **Comments:**
> **username_1**: I'm not sure I understand. You are given a language (in what form) and wish to compute a grammar for it ?  
> **username_2**: Perhaps you could give a bit more information/context. What classes of grammars/languages are you interested in (regular, context-free, ...)? Is there a specific language you're interested in, or otherwise what is your motivation?  
> **username_0**: @username_1,  right, I'm given a some language, which is described in general form (as a function, f.e.). And I need to write a grammar for this language.  
> **username_0**: @username_2,  I'm interested in all types of grammar, but mostly in Typ-3 (regular grammar and it's languages).   For example, I need to find a grammar for $a^{n}b^{n}c^{n}$ language. And my questions are:   - can we decide at first sight, which grammar we should use? If yes,  - how should we find the right amount of variables?  I know, that this language can be generated by Typ1-Grammar (context-sensitive). And I have it's grammar. But want to learn how to be able to find it by myself.  So.. is there any strategy for grammar derivation? Maybe something to every types of them or at least for regular.  
> **username_1**: I originally thought the problem was to *automatically* determine a grammar from a language spec. It now sounds more like you want help in *thinking* up a grammar from a language spec. This latter question I think is a little out of scope for this site, since it really pertains to basic tools in automata theory, not research-level questions in the area.  
> **username_3**: @SureshVenkat , what if the question was "automatically" determine a grammar from a language ? what would be the answer ? Or in another words for example given a regular expression (as in PCRE) how to determine which grammar to validate the strings in that language ?  

---

## 0 answers

