Formal Languages and Automata

[Apprentice123]

G = ( {S,A,B}, {a,b}, P, B) - B should be the starting variable.

Thank you very much!
I have another question: How to determine a grammar equivalent to another grammar?

[bobdark]

If you mean for a computer to determnine whether two grammars are equivalent - it can be done in a very very very small and tiny group of cases. Its impossible as far as I know though, to program a computer, that given two grammars, to decide whether they are equivalent or not.
If you're talking how a human can do that, by proving that for both of the grammars for each word one derives, the other one can derive the same word.
To speak formally, you have to prove:
1) L(G1) ⊆ L(G2)
2)L(G2) ⊆ L(G1)
That is, if by saying equivalent you mean that they produce the same language.

[Apprentice123]

If you mean for a computer to determnine whether two grammars are equivalent - it can be done in a very very very small and tiny group of cases. Its impossible as far as I know though, to program a computer, that given two grammars, to decide whether they are equivalent or not.
If you're talking how a human can do that, by proving that for both of the grammars for each word one derives, the other one can derive the same word.
To speak formally, you have to prove:
1) L(G1) ⊆ L(G2)
2)L(G2) ⊆ L(G1)
That is, if by saying equivalent you mean that they produce the same language.

Ok. Thank you.
I was thinking if the language L = { a^n b^n c^n | n>=0 }
Three letters there is the possibility of creating a grammar?

[bobdark]

That is an interesting question. I don't know the precise answer. I can say that there is no context - free grammar for this language, i.e. grammar whos rules are of form V->a, where V is a variable and a is a string of terminals and variables. Context free means that you don't need anything "to surround" V to apply the rule. Why there is no context - free grammar? Read in wikipedia about: regular languages, context free languages and grammars, pumping lemma. I really have no idea whether there exists a non-context-free grammar that can derive this language. I'd be happy to know that too.

[Apprentice123]

That is an interesting question. I don't know the precise answer. I can say that there is no context - free grammar for this language, i.e. grammar whos rules are of form V->a, where V is a variable and a is a string of terminals and variables. Context free means that you don't need anything "to surround" V to apply the rule. Why there is no context - free grammar? Read in wikipedia about: regular languages, context free languages and grammars, pumping lemma. I really have no idea whether there exists a non-context-free grammar that can derive this language. I'd be happy to know that too.

I tried a few derivation, I could not solve.
S -> aAbBc
A -> ab
B -> c

It only works for n = 1

[bobdark]

Its a context free grammar. Context free grammar CANNOT derive that language. Theres a proof of this claim.
A non context free grammar can though -
E->aSS'bD
S->aSS'b
S'b->bS'
S'D->DS'
DS'->Dc
D->epsilon

The idea is to derive same number of a's, b's and S'. Then move each S' to the end of the word and derive c for each S'.

[Apprentice123]

I found the Internet to written language differently
L = { wcw | w is word of {a,b}*}

How to develop a grammar for that language?

[bobdark]

Ill leave for you to figure it out alone, based on the grammar for a^nb^nc^n that I've written.
Basically a non-context free grammar is equivalent to a turing machine if Im not mistaken.
One way to do it MAY be thinking how would a computer program for deriving those words look like ad try and implement it in grammars. This might be a bit hard though. You may also try to think how would an algorithm for a turing machine look like and try to import it to the grammars. This is very abstract tips but I can't think of another way I could help you.
The fact that the grammar has to be non-context free means that you must non-context free derivation rules to insure that some terminals or variables will be derived in specific locations, and thus restrict the order of applying derivation rules.

[Apprentice123]

L = { a^n b^n c^n | n>=0 }

I did
S -> XYZ
X -> XaA | F
Aa -> aA
AY -> YbB
Fa -> aF
FY -> epsilon
BZ -> c
Bb -> bB
BB -> BZB
Correct ?

You have ideia of how to get the solution with L = { www | w is word of {a,b}*} ?


Another question:

How to determine a grammar that generates e-mail?

Example: jack2.program.crazy@cc.lol.gg

[satyakarn]

grammar to produce tokens of C++

plzz help me regarding this...