1
$\begingroup$

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..

$\endgroup$
  • 2
    $\begingroup$ I'm not sure I understand. You are given a language (in what form) and wish to compute a grammar for it ? $\endgroup$ – Suresh Venkat Oct 26 '11 at 16:03
  • 2
    $\begingroup$ 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? $\endgroup$ – Max Oct 26 '11 at 17:54
  • $\begingroup$ @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. $\endgroup$ – Lissa Oct 27 '11 at 8:50
  • $\begingroup$ @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. $\endgroup$ – Lissa Oct 27 '11 at 8:53
  • 3
    $\begingroup$ 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. $\endgroup$ – Suresh Venkat Oct 27 '11 at 18:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.