Context-free Grammars.

  • (2 Pages)
  • +
  • 1
  • 2

16 Replies - 1512 Views - Last Post: 27 May 2016 - 02:49 PM

#1 mydiax  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 9
  • Joined: 26-May 16

Context-free Grammars.

Posted 26 May 2016 - 01:39 AM

I'm just getting into CS112. I know there's a way to express programs made by software engineers with mathematical symbols. Context-free grammar, would be one of them and this is on stack exchange but haven't gotten an answer yet. Is there a website or a book I can buy to try and map out programs that I would like to test out during the summer to try and get ahead? I'm fairly intellectual, but I don't know the name for the style of using mathematic symbol to define; array, int [E| {matrix}]

I was following through with some CFG, but I'm still not seeing what the word is for the type, before CFG is needed. I understand that m^n && n^m = mm + nn; since the && applies both log[subx]n^m + log[subx]m^n but this is where I don't follow (mind you I'm Algebra II). nth -> (pointer) m, nth -> n assigns both value and address...so is that how C++ uses copy using the equal sign for strings instead of strcpy? That's the main idea of CFG right?

Back to the question, is there anything related to this type of rationalizing with mathematic symbols?

Is This A Good Question/Topic? 0
  • +

Replies To: Context-free Grammars.

#2 Peter O  Icon User is offline

  • D.I.C Regular

Reputation: 128
  • View blog
  • Posts: 298
  • Joined: 19-October 13

Re: Context-free Grammars.

Posted 26 May 2016 - 02:40 AM

A context-free grammar doesn't describe a program, it describes what the valid syntax of a language is. Note that C++ is not a context-free language so it can't be fully described using a context-free grammar.
Was This Post Helpful? 0
  • +
  • -

#3 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2503
  • View blog
  • Posts: 3,955
  • Joined: 21-June 11

Re: Context-free Grammars.

Posted 26 May 2016 - 07:17 AM

View Postmydiax, on 26 May 2016 - 10:39 AM, said:

I know there's a way to express programs made by software engineers with mathematical symbols. Context-free grammar, would be one of them


Context-free grammars are equivalent in power to (non-determistic) push-down automata, which are strictly less powerful than Turing machines. In order to model arbitrary computations (i.e. express arbitrary programs), you'd need a Turing machine or an equally powerful model of computation (such as unrestricted grammars, the lambda calculus, or a programming language).

Note that in practice CFGs are most often used to describe the syntax of programming languages, not to model computation.

Quote

Is there a website or a book I can buy to try and map out programs that I would like to test out during the summer to try and get ahead? I'm fairly intellectual, but I don't know the name for the style of using mathematic symbol to define; array, int [E| {matrix}]


I did not understand that part of your question.

Quote

I was following through with some CFG, but I'm still not seeing what the word is for the type, before CFG is needed.


I'm not sure I understand you, but if you mean "What can I use when I don't need the power of CFGS, i.e. what's a less powerful model than CFGs?", then that'd be regular grammars, regular expressions and finite automata (all of which are equivalent in power).

[quote]I understand that m^n && n^m = mm + nn; since the && applies both log[subx]n^m + log[subx]m^n[quote]

Huh?

Quote

but this is where I don't follow (mind you I'm Algebra II). nth -> (pointer) m, nth -> n assigns both value and address...so is that how C++ uses copy using the equal sign for strings instead of strcpy? That's the main idea of CFG right?


Those things have nothing to do with each other. C++ strings can be copied using the = operator because the string class overloads the = operator to do that. This particular overload is implemented in the C++ standard library (which is specified in the C++ language standard) and the semantics of the operator overloading feature that make this possible are also defined in the C++ language standard (using plain English sentences - grammars are only used to define the syntax).

If your question (which to be honest is almost entirely unclear to me at this moment) is how one could describe such features using mathematical notation rather than English sentences, you should look into formal semantics.
Was This Post Helpful? 1
  • +
  • -

#4 macosxnerd101  Icon User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12134
  • View blog
  • Posts: 45,117
  • Joined: 27-December 08

Re: Context-free Grammars.

Posted 26 May 2016 - 07:20 AM

Moved to Computer Science. This is not a C/C++ question.

I would suggest a textbook like Sipser or Ullman-Hopcroft for theory, and a book like Ullman's Compilers text for practice on how CFGs are applied.
Was This Post Helpful? 0
  • +
  • -

#5 mydiax  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 9
  • Joined: 26-May 16

Re: Context-free Grammars.

Posted 26 May 2016 - 12:30 PM

[quote name='sepp2k' date='26 May 2016 - 07:17 AM' timestamp='1464272226' post='2259137']
[quote name='mydiax' date='26 May 2016 - 10:39 AM' timestamp='1464251968' post='2259082']
I know there's a way to express programs made by software engineers with mathematical symbols. Context-free grammar, would be one of

[quote]I understand that m^n && n^m = mm + nn; since the && applies both log[subx]n^m + log[subx]m^n

Quote

Huh?

Quote

but this is where I don't follow (mind you I'm Algebra II). nth -> (pointer) m, nth -> n assigns both value and address...so is that how C++ uses copy using the equal sign for strings instead of strcpy? That's the main idea of CFG right?


Those things have nothing to do with each other. C++ strings can be copied using the = operator because the string class overloads the = operator to do that. This particular overload is implemented in the C++ standard library (which is specified in the C++ language standard) and the semantics of the operator overloading feature that make this possible are also defined in the C++ language standard (using plain English sentences - grammars are only used to define the syntax).

If your question (which to be honest is almost entirely unclear to me at this moment) is how one could describe such features using mathematical notation rather than English sentences, you should look into formal semantics.


5^2 = 25

= 7

2^5 = 32
_______
4^3 = 64

= 17

3^4 = 81
_______
3^5 = 243

= 118

5^3 = 125
_______

[25 + 32] - [118 - 81] + [243] = 101 + [17] = 118 + [7] = [125]

+ [118] = 243? Is this logarithms?

I see CFG as strings for hash, output and input but don't know how to express it. I also see CFG as logs.
Was This Post Helpful? 0
  • +
  • -

#6 mydiax  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 9
  • Joined: 26-May 16

Re: Context-free Grammars.

Posted 26 May 2016 - 01:20 PM

I think you answered my question. When the computer or language was made, they created a 'semantic' (don't quote me) that follows per se the allocation of hashes defined by an equivalent encryption (later on I believe would be the internet?) I see logarithms in CFG, I see hash in CFG. I just don't know how to express the allocation or substitution when it inherits something.

When I look at Context-free Grammar, When I said, "define; array, int [E|{matrix}]" there has to be a better way to allocate strings or characters of strings like CFG. When you have certain strings that 'do' a specific thing, initiate a specific value or store a huge amount of data (SHA-1, SHA-2, SHA-3), the computer is broken down into tiny little concepts. For instance, mathematics being nature or man-made, who was to say we would have a computer, but no internet, or internet but no domain?

Below is a quote I found from looking at:

m^n && n^m = mm + nn; since the && applies both log[subx]n^m + log[subx]m^n but this is where I don't follow (mind you I'm Algebra II). nth -> (pointer) m, nth -> n assigns both value and address.
Giving the fact that a pointer in C++ will give value if you use a structure and void, instead it would give you the memory address. There has to be a way to write this down mathematically it would make things so much easier. Until when someone has a better answer on how to incorporate arrays into hash, from hash into logs, and logs into an algorithm then algorithm into binary decay. (Which I believe is "Discrete Structures"). This is the best answer I could find, since from the comments I believe it probably will never exist until someone figures out geometric sequencing. I was told you would just need a "Turing machine" to do this, if an expression for that even exists.

Quote

5^2 = 25

= 7

2^5 = 32

4^3 = 64

= 17

3^4 = 81

3^5 = 243

= 118

5^3 = 125

125 - 243 + 32 - 118 - 81 + 243 = 0/?

[25 + 32] - [118 - 81] + [243] = 101 + [17] = [118 + 7] = [125] plus

[118] = [243] notice this specific way gives you the "inverse" function I believe would be called of m^n and n^m.

Was This Post Helpful? 0
  • +
  • -

#7 macosxnerd101  Icon User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12134
  • View blog
  • Posts: 45,117
  • Joined: 27-December 08

Re: Context-free Grammars.

Posted 26 May 2016 - 01:45 PM

The -> operator in C++ means something very different than when talking about grammars. In formal languages, the right arrow -> has the head of the rule to its left and the body on the right.

Quote

There has to be a way to write this down mathematically it would make things so much easier. Until when someone has a better answer on how to incorporate arrays into hash, from hash into logs, and logs into an algorithm then algorithm into binary decay.

A lot of this does not really make sense, but it's good that you're interested and engaging in it. If you want to get a feel for how to design programming languages and compilers, check out Ullman's Compilers text. It is the standard and very good. A hash function, formally is a function f : N -> N (where N is the set of natural numbers). A hash function is computable.

The logarithm can be approximated to an arbitrary \epsilon > 0 by a convergent sequence of rational numbers (you should see series and sequences in precalculus), such as the Taylor Series approximation. From a syntactic point of view, you could define grammatical rules to handle function syntax, if that's what you're interested in. Computing irrational numbers is well, a challenge, because models of computation (ignoring hypercomputation) deal with finite strings.

Turing Machines can be represented in binary, as we can represent Turing Machines as strings. Roughly speaking, a Turing Machine is equivalent to an algorithm.


Unfortunately, a lot of this material isn't immediately accessible because you are in Algebra II. Getting through precalculus will help a lot. It's likely you could engage with some discrete math though. Epp's textbook on discrete math is excellent and approachable. There is a lot of good material in there, including a section on automata theory I believe. I would also suggest spending some time on things like basic logic, set theory, number theory, combinatorics, graph theory, and basic complexity. If memory serves, Epp has sections on most or all of these subjects.

The material you are talking about is really a senior level course in CS undergraduate programs. Theory of Computation is one of the hurdle courses. When you get to college, I think you would really benefit from double majoring in CS and Math. The Math major will give you a lot of tools like algebra, topology, and analysis, as well as maturity to engage in theoretical computer science. Basically, CS theory is just math. So you will be very well prepared by your senior year with a double major.

I hope this helps some!
Was This Post Helpful? 1
  • +
  • -

#8 mydiax  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 9
  • Joined: 26-May 16

Re: Context-free Grammars.

Posted 26 May 2016 - 01:49 PM

Thank you though, for formal logic and semantic.

I don't believe an expression for Turing machine will ever exist. He died awhile ago, I doubt he completed the algorithm? It said modern day CPU's use some form of this model, but those are business secrets.

Thank you Mac for clearing the lambda calculus up. I was afraid of getting into that just yet. It seems much easier as you just explained it. I'm bookmarking this!
Was This Post Helpful? 0
  • +
  • -

#9 macosxnerd101  Icon User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12134
  • View blog
  • Posts: 45,117
  • Joined: 27-December 08

Re: Context-free Grammars.

Posted 26 May 2016 - 01:54 PM

Quote

I don't believe an expression for Turing machine will ever exist.

A (deterministic) Turing Machine is a tuple (Q, \Sigma, \Gamma, \beta, q_{0}, \delta, F) where:
- Q is the finite set of states
- \Sigma is the input alphabet
- \Gamma is the tape alphabet
- \beta is the blank symbol which is not in \Gamma
- q_{0} is the initial state
- \delta : Q x \Sigma -> Q x (\Gamma U { \beta } ) x { L, R, S } is the state transition function
- F \subset Q is the set of accepting states

We can represent each of these components, and so we can represent the Turing Machine as a string. It is not hard to convert a string to binary.

Quote

Thank you Mac for clearing the lambda calculus up. I was afraid of getting into that just yet. It seems much easier as you just explained it. I'm bookmarking this!

I'm glad I could help! :)
Was This Post Helpful? 0
  • +
  • -

#10 mydiax  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 9
  • Joined: 26-May 16

Re: Context-free Grammars.

Posted 27 May 2016 - 02:59 AM

I wanted to show an example of what I'm talking about.

I didn't think I could use Turing's machine to express certain points.

This is about a geometric stability between two triangles: you can view the whole code on my website link. :)/>/>/>/>

There are way too many coincidences that make this very unusual. Yes I spend a lot of time with a calculator. Quote because it shows smilies.

4 * 4680 / 1170 = 16; c**2 * c**2;

4680b / 1170b = c**2; 4;

4680b / 1170b * 1170b = 4680b

4680b / 1170b = 4; c**2;

1170 * 4 = 4680b / 1170b = 4; z;

z = 90ab - 13b
z /= /0 as ab*

16200ab - 8100ab + 45ab + 1800ab


1440 = f(x) = z(s(f(x));
90ab - 13b(180 - 90 * 50% + b: 20) = (2340b - 1170b) * 6.5b + 260b = 2340b / 360 = 6.5; [90 * 13 = 1170 * 20 = 23,400 / 360 = 65; 65 * 260 = 16,900 * 36x / 26; 23,400, 1440(65) / 360; = 260 * 10% = 26; 16,900 / 13 = 1300
]

ab{1} * b{1} = b{2} * b = 23,400 / 360 = d; d * 260{1440 * 65 = 93,600 / 360 = 260;} = 16,900 * 36x / 26{1440(65) / 360; = 260 * 10% = 26}; 23,400; d * 260 = 16,900 * 36 / 26 = 23,400;

ab{1} * b{1} = b{3} * [x]/[] = d
b{1} * {b} = [x]
[x] / 360 = d;
d * {260 as q} = {q1}
{q1} * {36x not array} / {26 as q{3}} = b{2}
{E = 1440(65) / 360; = 260 * 10% = 26}
{q1} / {13 as {q{4}} = {x = 2340 / {b} * {a} / {a + b}; {a * {a / a + b} * {2b} / (a + b + a + B ) = {q1} / {q4}

ab{1} * b{1} = b{3}
b{1} * {b} = [x]
[x] * (a + b + a + B ) = d;
d * {q} = {q1}
{q1} * {x::x} / {q3} = b{3}
d * {E = 1440(65) / 360; = 260 * 10% = 26} / {q4} = +(E);
E = {q3}[E = e{count}] = -b{2} / {b} * {a1} / {a + b} * {a2} {b::2} / {a + b + a + b} = -(E);


Data mining into -2340, it turns to be prime when in relation to 20, and 160 doesn't give a specific answer. 2340/20 is 117. 117 * 160 which is "a" in the first set, is 18,720 divide by 180 is 104. Taking the second part "a" which is 150, 150 * 104 = 15,600 and times that by the second part "b" which is 30, 15,600 * 30 = 468,000 divide by circle, 360, 468,000 / 360 is 1,300. / 1170 = 16; c**2 * c**2;

4680b / 1170b = c**2; 4;

4680b / 1170b * 1170b = 4680b

4680b / 1170b = 4; c**2;

1170 * 4 = 4680b / 1170b = 4; z;

z = 90ab - 13b
z /= /0 as ab*

16200ab - 8100ab + 45ab + 1800ab


1440 = f(x) = z(s(f(x));
90ab - 13b(180 - 90 * 50% + b: 20) = (2340b - 1170b) * 6.5b + 260b = 2340b / 360 = 6.5; [90 * 13 = 1170 * 20 = 23,400 / 360 = 65; 65 * 260 = 16,900 * 36x / 26; 23,400, 1440(65) / 360; = 260 * 10% = 26; 16,900 / 13 = 1300
]

ab{1} * b{1} = b{2} * b = 23,400 / 360 = d; d * 260{1440 * 65 = 93,600 / 360 = 260;} = 16,900 * 36x / 26{1440(65) / 360; = 260 * 10% = 26}; 23,400; d * 260 = 16,900 * 36 / 26 = 23,400;

ab{1} * b{1} = b{3} * [x]/[] = d
b{1} * {b} = [x]
[x] / 360 = d;
d * {260 as q} = {q1}
{q1} * {36x not array} / {26 as q{3}} = b{2}
E = 1440(65) / 360; = 260 * 10% = 26}
{q1} / {13 as {q{4}} = {x = 2340 / {b} * {a} / {a + b}; {a * {a / a + b} * {2b} / (a + b + a + b ) = {q1} / {q4}

Quote

ab{1} * b{1} = b{3}
b{1} * {b} = [x]
[x] * (a + b + a + b ) = d;
d * {q} = {q1}
{q1} * {x::x} / {q3} = b{3}
d * {E = 1440(65) / 360; = 260 * 10% = 26} / {q4} = +(E);
E = {q3}[E = e{count}] = -b{2} / {b} * {a1} / {a + b} * {a2} {b::2} / {a + b + a + b } = -(E);


+ and - E is two different types from E = E; E can either have a positive value or negative. But they are the same value.

-1300 or 1300. One is model, one is computational connection. But there are two different ways to get there from the same numbers, but way different path. (not technically the same numbers they all have reason).


-E =


Quote

Data mining into -2340, it turns to be prime when in relation to 20, and 160 doesn't give a specific answer. 2340/20 is 117. 117 * 160 which is "a" in the first set, is 18,720 divide by 180 is 104. Taking the second part "a" which is 150, 150 * 104 = 15,600 and times that by the second part "b" which is 30, 15,600 * 30 = 468,000 divide by circle, 360, 468,000 / 360 is 1,300.


Uh sorry, don't know how to edit. Forgot to edit out some of the text.
Was This Post Helpful? 0
  • +
  • -

#11 macosxnerd101  Icon User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12134
  • View blog
  • Posts: 45,117
  • Joined: 27-December 08

Re: Context-free Grammars.

Posted 27 May 2016 - 08:48 AM

To be fair, you cannot express an uncountable number of points using any (implementable) model of computation. The irrationals cannot be represented on a computer, only approximated.

The Fundamental Theorem of Arithmetic guarantees that each positive integer has a unique prime factorization. It's quite easy to group these factors and obtain new factors.
Was This Post Helpful? 0
  • +
  • -

#12 mydiax  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 9
  • Joined: 26-May 16

Re: Context-free Grammars.

Posted 27 May 2016 - 12:14 PM

But it's if the factor does a task correct?

If prime is the only unique product, Fibonacci is the only real algorithm programmers need correct?

Say, I have a math string, lets say this: http://mathworld.wol...com/String.html

Quote

A string of length n on an alphabet l of m characters is an arrangement of n not necessarily distinct symbols from l. There are m^n such distinct strings.

For example, the strings of length n=3 on the alphabet {1,2} are {1,1,1}, {1,1,2}, {1,2,1}, {1,2,2}, {2,1,1}, {2,1,2}, {2,2,1}, and {2,2,2}.

In the Wolfram Language, strings of length n in the alphabet consisting of the members of a list l can be enumerated using Tuples[list, n].


If I have a two-dimensional array, which is basically a matrix within a math string correct?

In all essence, you are saying that any evolution from a number is equally obsolete because not only can it be factored, but easily. If all the products and sums are equivalent to the answer to a matrix or "array", which I know are not the same thing.

If I had (algebra II mind): string = "abbabbgg";

and a math string: ab: gg;

matrix: aa bb aa bb
gg gg gg gg
bb bb bb bb
ab ab ab ab

and - F \subset Q is the set of accepting states;

q as: "babggbab"
q as: "aabaabgg"
q as: ...

eventually yes it is factored, but can't you put a log within a variable within q's substring?

b = log(x) * x^2;
b = b.substr(0, 1);
a = log(n) * x^2;
a = a.substr(0, 1);
g = a + b;
g = g.substr(0, 7)

you cannot factor a variable within a string right?
Was This Post Helpful? 0
  • +
  • -

#13 macosxnerd101  Icon User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12134
  • View blog
  • Posts: 45,117
  • Joined: 27-December 08

Re: Context-free Grammars.

Posted 27 May 2016 - 01:32 PM

Quote

But it's if the factor does a task correct?

If prime is the only unique product, Fibonacci is the only real algorithm programmers need correct?

This is nonsense. In the ring of integers, each positive integer has a unique prime factorization. A factor of the integer n is another integer k such that kq = n, for some third integer q. The integer k is said to be prime if it has positive no factors other than itself and 1.

Not to be rude, but everything you just wrote about factoring strings is also nonsense. The set of finite strings forms a semigroup under the operation of string concatenation. That means string concatenation is an associative, binary operation. We can define what we mean by a factor in some analogous manner as for the integers. It makes a little less sense to talk about prime factors of strings. You really need some abstract algebra under your belt if we're going to engage in this, though. Judson's text is free, online, and a very good starting point. Granted, abstract algebra is probably quite a reach given that you're in Algebra II.

Quote

you cannot factor a variable within a string right?

Are you talking about C++ or math?

Regarding Turing Machines, states are not input strings.
Was This Post Helpful? 1
  • +
  • -

#14 mydiax  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 9
  • Joined: 26-May 16

Re: Context-free Grammars.

Posted 27 May 2016 - 01:35 PM

[g] as log (2 log x^log (n)) = log (n) + log (x) = 2? (log(x) * x^2 is just X to prep another variable within a math string right?

But m^n && n^m = mm + nn; since the && applies both log[subx]n^m + log[subx]m^n I'm lost here

(0, 7) applies g = m[x] + n[x] as mmmm + xxxx;

x^2 is xx log n^m nn

xxnn, xxmm

x has to be defined by a number...and I haven't taken any precalculus courses. Because the only way in programming to do a variable in a string is if the variable is a number. That would link it backwards all the way to

q as: "babggbab"
q as: "aabaabgg"
q as: ...

so, if(x) = num; return false; (is this a double negative for g = m[x] + n[x])
if(x = false) return num; ?

is there a way to generate a random number within your own hash?
Was This Post Helpful? 0
  • +
  • -

#15 macosxnerd101  Icon User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12134
  • View blog
  • Posts: 45,117
  • Joined: 27-December 08

Re: Context-free Grammars.

Posted 27 May 2016 - 01:41 PM

I have literally no idea what you are talking about. You're rambling, and it makes absolutely no sense.

You're jumping between implementing a computer algebra system to Turing Machines and CFGs to prime factorizations to hashing. It's hard to point you in a direction because you are running around like a chicken with it's head cut off.
Was This Post Helpful? 1
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2