Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Theory Of Computation - PDA to CFG
New Posts  All Forums:Forum Nav:

Theory Of Computation - PDA to CFG

post #1 of 3
Thread Starter 
For some reason I cant do the small symbols here so here is the PDA I am trying to convert into CFG http://imgur.com/cnhuHCX

𝐿={𝜔| 𝜔=𝑎𝑘𝑏𝑛𝑐𝑘−𝑛}

My question is, does the CFG say c has the same amount of a but there are more b as c has a -n?

So there should be more b then a and c?
post #2 of 3
Okay so you can describe this as:

Givens:

1. There exists the characters, 'a', 'b', and 'c' that generate a word, ω.

2. The order of the words generated will be a's, followed by b's, and then followed by c's.

3. The number of a's is some integer value k, that is a ∈ N (aka integer values >= 0).

4. The number of b's is some integer value n, that is b ∈ N (aka integer values >= 0).

5. The number of c's is some integer value k - n, that is c ∈ N (aka integer values >= 0).


Assumptions:

1. Since there needs to be at least zero c's, then it must be true that k - n >= 0. Therefore it must be true that k >= n.

2. I am assuming that we are not talking about negative integer variables k ∉ ℤ and n ∉ ℤ, but are natural numbers subset of ℤ, k ∈ N and n ∈ N.


Examples of generated words, ω:

k = 0, n = 0: ϵ

k = 1, n = 1: ab

k = 1, n = 0: ac

k = 2, n = 1: aabc

k = 2, n = 0: aacc

k = 2, n = 2: aabb

k = 3, n = 2: aaabbc

k = 3, n = 1: aaabcc

k = 3, n = 0: aaaccc
....... etc ......


I won't finish the assignment for you but I hope you get the gist of it. If you haven't please let me know. biggrin.gif

**EDIT**

One big tip, create the state machine graph of the Pushdown Automata on paper to understand the state transitions then you will understand what is required to describe the Context Free Grammar.
Edited by adramalech707 - 10/28/15 at 3:42pm
Intel build
(17 items)
 
  
CPUMotherboardGraphicsRAM
i7 860 gigabyte p55-ud6 gigabyte gv-n560oc-1gi Corsair Vengeance CMZ8GX3M2A1600C9 
Hard DriveHard DriveHard DriveOptical Drive
Crucial M4 WD Caviar Black WD Caviar Black LiteOn Lightscribe 24x 
CoolingOSMonitorMonitor
Thermaltake Frio Extreme CLP0587 Arch Linux x86_64 samsung 2243swx ASUS vs-248H-p 
KeyboardPowerCaseMouse
moditek led flex Seasonic 860Watt Platinum Antec Lanboy air razor death adder 
  hide details  
Reply
Intel build
(17 items)
 
  
CPUMotherboardGraphicsRAM
i7 860 gigabyte p55-ud6 gigabyte gv-n560oc-1gi Corsair Vengeance CMZ8GX3M2A1600C9 
Hard DriveHard DriveHard DriveOptical Drive
Crucial M4 WD Caviar Black WD Caviar Black LiteOn Lightscribe 24x 
CoolingOSMonitorMonitor
Thermaltake Frio Extreme CLP0587 Arch Linux x86_64 samsung 2243swx ASUS vs-248H-p 
KeyboardPowerCaseMouse
moditek led flex Seasonic 860Watt Platinum Antec Lanboy air razor death adder 
  hide details  
Reply
post #3 of 3
Thread Starter 
Quote:
Originally Posted by adramalech707 View Post

Okay so you can describe this as:

Givens:

1. There exists the characters, 'a', 'b', and 'c' that generate a word, ω.

2. The order of the words generated will be a's, followed by b's, and then followed by c's.

3. The number of a's is some integer value k, that is a ∈ N (aka integer values >= 0).

4. The number of b's is some integer value n, that is b ∈ N (aka integer values >= 0).

5. The number of c's is some integer value k - n, that is c ∈ N (aka integer values >= 0).


Assumptions:

1. Since there needs to be at least zero c's, then it must be true that k - n >= 0. Therefore it must be true that k >= n.

2. I am assuming that we are not talking about negative integer variables k ∉ ℤ and n ∉ ℤ, but are natural numbers subset of ℤ, k ∈ N and n ∈ N.


Examples of generated words, ω:

k = 0, n = 0: ϵ

k = 1, n = 1: ab

k = 1, n = 0: ac

k = 2, n = 1: aabc

k = 2, n = 0: aacc

k = 2, n = 2: aabb

k = 3, n = 2: aaabbc

k = 3, n = 1: aaabcc

k = 3, n = 0: aaaccc
....... etc ......


I won't finish the assignment for you but I hope you get the gist of it. If you haven't please let me know. biggrin.gif

Thank you! Yes, I figured it out yesterday! But thanks for replying! I really didnt understand when I posted this, but then I a bit more research and found out that its really easy!

I really appreciate it though! We did get the same answer!
New Posts  All Forums:Forum Nav:
  Return Home
  Back to Forum: Coding and Programming
Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Theory Of Computation - PDA to CFG