3

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.

Improve this question
20
  • 1
    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, 2017 at 19:29
  • 2
    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, 2017 at 0:07
  • 3
    I'm voting to close this question as off-topic because it really belongs on cs.stackexchange.com
    – Mitch
    Jan 29, 2017 at 1:09
  • 4
    Furthermore, the answer to the second question is already here : math.stackexchange.com/questions/566382/…
    – Typhon
    Jan 29, 2017 at 1:37
  • 3
    @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.
    – Natalie Clarius
    Jan 29, 2017 at 10:29

3 Answers 3

Reset to default
2

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
AD -> AC
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?

About topic:

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.

Improve this answer
1

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.

Improve this answer
5
  • 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.
    – Natalie Clarius
    Jan 28, 2017 at 22:25
  • @lemontree, Sorry. I often use "phrase structure grammar" to mean "context free phrase structure grammar".
    – Greg Lee
    Jan 28, 2017 at 22:30
  • 1
    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, 2017 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, 2017 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).
    – Natalie Clarius
    Jan 29, 2017 at 10:34
0

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

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.