# What grammar generate this sequence

I need some little help in connection with linguistics.

My first question is: Is there any fast way to figure out grammar if I have sequence of symbols, or do I have to guess?

My second question is: Given the following language, what is a phrase structure grammar that produces this language?

L = {x^(2^i) : i >= 0}


This language contains the follwing sequences:

x
xx
xxxx
...


I started with something like this:

G = (V,T,P,S)

V = {A, ... }

T = {x}

P = {

S -> A
...
}


Can anybody help with completing the grammar?

For example, the grammar for the language defined as

L2 = {x^i : i > 0}


is

G = (V,T,P,S)

V = {A}

T = {x}

P = { A -> x | xA }

S = A


I need to figure out a similar set of production rules P for the language defined above.

• Is your question "Is there an algorithm for inducing a grammar from a finite subset of the strings admitted by the grammar?" If so, no, because "xxxx" is a finite subset of the strings generated by infinitely many grammars. Or are you asking for a grammar that will generate the language characterized as x^(2^i)? In that case, the simplest such grammar is "x^(2^i)": but perhaps you have in mind a specific kind of grammar, so let us know what you are asking. – user6726 Jan 28 '17 at 19:29
• The question is about linguistincs theory - "Q&A for professional linguists and others with an interest in linguistic research and theory." I hope i didnt break any rule so iif you can't help do no harm – Hadson Jan 29 '17 at 0:07
• I'm voting to close this question as off-topic because it really belongs on cs.stackexchange.com – Mitch Jan 29 '17 at 1:09
• Furthermore, the answer to the second question is already here : math.stackexchange.com/questions/566382/… – Typhon Jan 29 '17 at 1:37
• @Mitch No, it doesn't. It's a question about formal syntax, so it's on-topic here. Phrase structure grammars are just as well applicable (and are in fact applied) to natural languages, so it asks about a formalism that is used in linguistics. Our help center says that this site is for the study of languages, and {x^(i^2)} is a language, so I see no reason to stipulate it off-topic. – lemontree Jan 29 '17 at 10:29

I found two answer, one in Hopcroft,Ullman's book there was set of productions contains 19 productions. Second solution i found on the internet:

S -> ACxB
Cx -> xxC
CB -> DB
CB -> E
xD -> Dx
xE -> Ex
AE -> \epsilon


I tryied with few examples and is seem to match but i'm not sure. Can you confirm if it is valid solution?

This question is connected with subject: Linguistics and formal languages(it isn't computer science subject) and no this isnt my homework. I found similar questions,topics in books designed for student non-technical universities.

I think the answer to your first question is that you have to guess. I don't think there is a context-free answer to your second question, as lemontree suggests in a comment. The language you are trying to generate is reminiscent of the "copy language", each sentence of which is a string concatenated to a copy of that string, and which (I gather) is shown to non-context free in the standard text by Hopcraft and Ullman. The "copy language" is supposedly the pattern of the cross serial constructions of Swiss German that Stuart Schieber uses in his argument that natural languages are not context free.

For whatever interest it may have, however, there is an answer to the second question in a system I invented, which is like phrase structure grammar, but has variables and constants rather than nonterminal and terminal symbols. If S is a variable and x is a constant, then the rules {S = SS, S = x} generate the language {x, xx, xxxx, ...}. This is because in ordinary algebraic systems, substitution for a variable must be uniform, in the sense that every occurrence of a variable in a formula must be substituted for in the same way. Variables are thought of as standing in place of a constant.

• I wasn't suggesting that there is no answer to the second question. I was only suggesting that the answer would not be context-free, but it is well possible that there is a (unrestricted or context-sensitive) phrase structure grammar that generates this language. – lemontree Jan 28 '17 at 22:25
• @lemontree, Sorry. I often use "phrase structure grammar" to mean "context free phrase structure grammar". – Greg Lee Jan 28 '17 at 22:30
• There is no requirement that this should be context-free grammar. I am study from hopcroft "Automata theory" 3rd edition. But couldn't find anything about this kind of grammars before i created this post ;/ Are you trying to say that there arent exists any simple set of production for this kinds of sequences? – Hadson Jan 28 '17 at 23:07
• I see. Well, I still don't know, but since type 0 grammars are Turing machine equivalents, it seems you ought to be able to do it, somehow. (In an early paper, Chomsky suggested that type 1 grammars didn't really merit the term "phrase structure grammar", since they allow operations that are not confined within phrases.) – Greg Lee Jan 29 '17 at 2:50
• @Greg Lee Not necessarily - just because TMs recognize type 0 languages doesn't mean that there must be a (type 0) grammar for this language; there are languages which are not recursively enumerable/TM recognizable at all (although I do think this language is at least type 0). – lemontree Jan 29 '17 at 10:34

The task you are talking about is called grammar induction and is the topic of much research in NLP.