Clever Geek Handbook

Contextual free grammar for unary complement

Given the alphabet from 1s, I want to analyze adding a shape

1^k + 1^j = 1^k+j

It's pretty easy to imagine using a trigger by simply pushing 1 on the stack on each of the first two 1s and then on the last set of 1s. However, I can't figure out how to represent this as a context free grammar, which is obviously possible with PDA == CFG.

+2


source to share


8 answers


My advice is to make a simple starting point: 1 + 1 = 11 And now try to figure out how you can “grow” that with legal CFG expressions.

Alternatively, I solved this now by trying to expand it with "matching brackets", which is a common problem with CFG implementation. Its obviously more difficult, but you can find such a fruitful path.



Hope this helps! Happy hunting.

Eigor

+1


source


If you rewrite RHS as 1^j1^k

, then you should only see two nested sets of balanced 1

s. Combined with the "base body" 1 + 1 = 11

you should be able to grow "j" s on the inside and "k" outside.



+2


source


Generic unary append is not possible with context free grammar or with a popping machine. For this type of computation, you must use a Turing machine. Writing a popping machine that pushes 1 onto the stack is invalid, because the stack is not an output of the PDA. The only output of the PDA is a binary "Accept" or "Reject", which indicates whether the input string is part of a language that is recognized by the PDA.

+2


source 


S => 1A1
A => 1A1 | +1B1
B => 1B1 | =

The first two lines build the first term and sum with the same number of ones. Once the first term is built, you will go to the second with "A => + 1B1". The third line constructs the second term while simultaneously adding an equal number of ones to the sum. Once you're done, the equals transition ends.

Note that this prevents any term in the expression from being zero. Alternatively, you can plot unary minus expressions with a slight modification, keeping in mind that a - b = c is equivalent to a = b + c

+2


source


Yes, this person has bothered me for the last hour.

Also, cdiggins, 1 + 1 = 111 will go through that

0


source


I've also worked on this forever and can't get it to work. this is what makes the most sense to me:

A → B + B = BB B → BB B → 1

but yes this takes strings like 1 + 111 = 11 and 11 + 1 = 111111 and other nonsense. people here seem to know but don't want to share. this is not something we can google and get meaningful help. Think you can be a little more helpful?

0


source 


S   ->  1 + 1 = 11
S   ->  1S1
S   ->  1 + 1A11
A   ->  1 = 1
A   ->  1A1
0


source


I know his old question, I read Gödel, Escher, Bach and was amazed at a similar problem (creating a gram for his pq system)

So, for the OP's question, I think the following production rules should do:

first → 1 + second1 | 1first1 second → 1 = 1 | 1second1

0


source






More articles:


All Articles