Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Help with Finite Automaton Question
New Posts  All Forums:Forum Nav:

Help with Finite Automaton Question

post #1 of 7
Thread Starter 
Hey guys, so I'm really struggling with a problem on finite automatons and we have a quiz based on our understanding of the question tomorrow. I was wondering if anyone could help me with the answer to part A. I honestly can't figure out why the example is incorrect.

Thanks a bunch and plus rep for quick help.

Attachment 232255

Edited by Varjo - 10/5/11 at 8:29pm
Balder
(16 items)
 
  
CPUMotherboardGraphicsRAM
i7 3770k @ 4.4ghz Gigabyte Sniper 3 (z77) EVGA 980ti SC+ ACX 2.0 16GB (2x8) Corsair Vengeance - 1600mhz 
Hard DriveHard DriveOptical DriveCooling
Crucial M4 (512MB) 4 x WD black 1TB LG Blueray Burner Corsair H100 
OSMonitorKeyboardPower
Windows 10 x64 Pro NEC Multisync 3090wqxi (2560x1600) Corsair k90 Corsair AX1200i 
CaseMouseAudioAudio
Corsair 600t white Naos 8200 Sennheiser HD 650 Zero DAC / Onkyo 875 
  hide details  
Reply
Balder
(16 items)
 
  
CPUMotherboardGraphicsRAM
i7 3770k @ 4.4ghz Gigabyte Sniper 3 (z77) EVGA 980ti SC+ ACX 2.0 16GB (2x8) Corsair Vengeance - 1600mhz 
Hard DriveHard DriveOptical DriveCooling
Crucial M4 (512MB) 4 x WD black 1TB LG Blueray Burner Corsair H100 
OSMonitorKeyboardPower
Windows 10 x64 Pro NEC Multisync 3090wqxi (2560x1600) Corsair k90 Corsair AX1200i 
CaseMouseAudioAudio
Corsair 600t white Naos 8200 Sennheiser HD 650 Zero DAC / Onkyo 875 
  hide details  
Reply
post #2 of 7
Thread Starter 
Updated OP.

Edit: Crap, this was supposed to be an edit. Sorry for the double post.
Balder
(16 items)
 
  
CPUMotherboardGraphicsRAM
i7 3770k @ 4.4ghz Gigabyte Sniper 3 (z77) EVGA 980ti SC+ ACX 2.0 16GB (2x8) Corsair Vengeance - 1600mhz 
Hard DriveHard DriveOptical DriveCooling
Crucial M4 (512MB) 4 x WD black 1TB LG Blueray Burner Corsair H100 
OSMonitorKeyboardPower
Windows 10 x64 Pro NEC Multisync 3090wqxi (2560x1600) Corsair k90 Corsair AX1200i 
CaseMouseAudioAudio
Corsair 600t white Naos 8200 Sennheiser HD 650 Zero DAC / Onkyo 875 
  hide details  
Reply
Balder
(16 items)
 
  
CPUMotherboardGraphicsRAM
i7 3770k @ 4.4ghz Gigabyte Sniper 3 (z77) EVGA 980ti SC+ ACX 2.0 16GB (2x8) Corsair Vengeance - 1600mhz 
Hard DriveHard DriveOptical DriveCooling
Crucial M4 (512MB) 4 x WD black 1TB LG Blueray Burner Corsair H100 
OSMonitorKeyboardPower
Windows 10 x64 Pro NEC Multisync 3090wqxi (2560x1600) Corsair k90 Corsair AX1200i 
CaseMouseAudioAudio
Corsair 600t white Naos 8200 Sennheiser HD 650 Zero DAC / Onkyo 875 
  hide details  
Reply
post #3 of 7
Not an FA expert, or amateur for that matter.

It says sigma represents all symbols. Does that include *?

If so, the transition from s(2) -> s(3) is not deterministic.

Of course if sigma represents all OTHER symbols not specified, that nukes my theory.

On second thought, this feels like the "correct" way. Explanation == difference between my graph and the original.



Edited by C-bro - 10/5/11 at 9:01pm
RAID0R
(14 items)
 
  
CPUMotherboardGraphicsRAM
i5 750 4.0GHz MSI P55-GD80 GTX 470 | 8800GT PhysX 2x2GB G.Skill Ripjaws 
Hard DriveOptical DriveCoolingOS
60GB Agility 2|1TB RAID0|1.5TB Pioneer DVR-217D XSPC Raystorm | XSPC RX240 Windows 7 Professional x64 
MonitorKeyboardPowerCase
27" Dell 2709W | 17" Samsung Logitech G15 Corsair HX850 Corsair 650D 
Mouse
Microsoft IntelliMouse 
  hide details  
Reply
RAID0R
(14 items)
 
  
CPUMotherboardGraphicsRAM
i5 750 4.0GHz MSI P55-GD80 GTX 470 | 8800GT PhysX 2x2GB G.Skill Ripjaws 
Hard DriveOptical DriveCoolingOS
60GB Agility 2|1TB RAID0|1.5TB Pioneer DVR-217D XSPC Raystorm | XSPC RX240 Windows 7 Professional x64 
MonitorKeyboardPowerCase
27" Dell 2709W | 17" Samsung Logitech G15 Corsair HX850 Corsair 650D 
Mouse
Microsoft IntelliMouse 
  hide details  
Reply
post #4 of 7
Thread Starter 
Quote:
Originally Posted by C-bro View Post
Not an FA expert, or amateur for that matter.

It says sigma represents all symbols. Does that include *?

If so, the transition from s(2) -> s(3) is not deterministic.

Of course if sigma represents all OTHER symbols not specified, that nukes my theory.

Yes it represents all symbols, but I don't believe that these have to be deterministic actually.
Balder
(16 items)
 
  
CPUMotherboardGraphicsRAM
i7 3770k @ 4.4ghz Gigabyte Sniper 3 (z77) EVGA 980ti SC+ ACX 2.0 16GB (2x8) Corsair Vengeance - 1600mhz 
Hard DriveHard DriveOptical DriveCooling
Crucial M4 (512MB) 4 x WD black 1TB LG Blueray Burner Corsair H100 
OSMonitorKeyboardPower
Windows 10 x64 Pro NEC Multisync 3090wqxi (2560x1600) Corsair k90 Corsair AX1200i 
CaseMouseAudioAudio
Corsair 600t white Naos 8200 Sennheiser HD 650 Zero DAC / Onkyo 875 
  hide details  
Reply
Balder
(16 items)
 
  
CPUMotherboardGraphicsRAM
i7 3770k @ 4.4ghz Gigabyte Sniper 3 (z77) EVGA 980ti SC+ ACX 2.0 16GB (2x8) Corsair Vengeance - 1600mhz 
Hard DriveHard DriveOptical DriveCooling
Crucial M4 (512MB) 4 x WD black 1TB LG Blueray Burner Corsair H100 
OSMonitorKeyboardPower
Windows 10 x64 Pro NEC Multisync 3090wqxi (2560x1600) Corsair k90 Corsair AX1200i 
CaseMouseAudioAudio
Corsair 600t white Naos 8200 Sennheiser HD 650 Zero DAC / Onkyo 875 
  hide details  
Reply
post #5 of 7
Edited the other post with what I think could be a correct graph. I think it ensures that a * must immediately follow a / in order to progress to s(2), and a / must immediately follow a * to progress to s(4). Otherwise you bounce back to s(0) or s(2) in those respective cases.

Again, all this is predicated on state transition analysis from sequential logic circuits. I have no idea if the same state transition principles transfer over to FA.
RAID0R
(14 items)
 
  
CPUMotherboardGraphicsRAM
i5 750 4.0GHz MSI P55-GD80 GTX 470 | 8800GT PhysX 2x2GB G.Skill Ripjaws 
Hard DriveOptical DriveCoolingOS
60GB Agility 2|1TB RAID0|1.5TB Pioneer DVR-217D XSPC Raystorm | XSPC RX240 Windows 7 Professional x64 
MonitorKeyboardPowerCase
27" Dell 2709W | 17" Samsung Logitech G15 Corsair HX850 Corsair 650D 
Mouse
Microsoft IntelliMouse 
  hide details  
Reply
RAID0R
(14 items)
 
  
CPUMotherboardGraphicsRAM
i5 750 4.0GHz MSI P55-GD80 GTX 470 | 8800GT PhysX 2x2GB G.Skill Ripjaws 
Hard DriveOptical DriveCoolingOS
60GB Agility 2|1TB RAID0|1.5TB Pioneer DVR-217D XSPC Raystorm | XSPC RX240 Windows 7 Professional x64 
MonitorKeyboardPowerCase
27" Dell 2709W | 17" Samsung Logitech G15 Corsair HX850 Corsair 650D 
Mouse
Microsoft IntelliMouse 
  hide details  
Reply
post #6 of 7
Thread Starter 
Quote:
Originally Posted by C-bro View Post
Edited the other post with what I think could be a correct graph. I think it ensures that a * must immediately follow a / in order to progress to s(2), and a / must immediately follow a * to progress to s(4). Otherwise you bounce back to s(0) or s(2) in those respective cases.

Again, all this is predicated on state transition analysis from sequential logic circuits. I have no idea if the same state transition principles transfer over to FA.

It is similar, but you don't need every path explicitly drawn. If there is no transition to take, then you do not accept the input.

In non deterministic situations, you can consider taking all choices at once, in effect having multiple "walkers" in your FA. Then, if some of them get stuck, they disappear, and ones that can take paths do.

Edit:

An input is considered "accepted" if, when the entire input has been parsed by the FA, there is at least one "walker" in an accepting state (even if there are others in non accepting states).
Edited by Varjo - 10/5/11 at 9:29pm
Balder
(16 items)
 
  
CPUMotherboardGraphicsRAM
i7 3770k @ 4.4ghz Gigabyte Sniper 3 (z77) EVGA 980ti SC+ ACX 2.0 16GB (2x8) Corsair Vengeance - 1600mhz 
Hard DriveHard DriveOptical DriveCooling
Crucial M4 (512MB) 4 x WD black 1TB LG Blueray Burner Corsair H100 
OSMonitorKeyboardPower
Windows 10 x64 Pro NEC Multisync 3090wqxi (2560x1600) Corsair k90 Corsair AX1200i 
CaseMouseAudioAudio
Corsair 600t white Naos 8200 Sennheiser HD 650 Zero DAC / Onkyo 875 
  hide details  
Reply
Balder
(16 items)
 
  
CPUMotherboardGraphicsRAM
i7 3770k @ 4.4ghz Gigabyte Sniper 3 (z77) EVGA 980ti SC+ ACX 2.0 16GB (2x8) Corsair Vengeance - 1600mhz 
Hard DriveHard DriveOptical DriveCooling
Crucial M4 (512MB) 4 x WD black 1TB LG Blueray Burner Corsair H100 
OSMonitorKeyboardPower
Windows 10 x64 Pro NEC Multisync 3090wqxi (2560x1600) Corsair k90 Corsair AX1200i 
CaseMouseAudioAudio
Corsair 600t white Naos 8200 Sennheiser HD 650 Zero DAC / Onkyo 875 
  hide details  
Reply
post #7 of 7
Quote:
Originally Posted by Varjo View Post
I honestly can't figure out why the example is incorrect.

Attachment 232255
It's been a while, but I agree with you. If non-determinism is OK, this first example seems valid.
TheHydra
(13 items)
 
  
CPUMotherboardGraphicsRAM
i7 860 @ 3.6 EVGA P55 FTW Sapphire TOXIC 2GB 6950 CORSAIR XMS3 4 x 2GB CMX4GX3M2A1600C7 
Hard DriveOSKeyboardPower
C300 64Gb + 2x F3 HD103SJ 1TB in RAID 0 Win7 x64 Razer BlackWidow Corsair 750HX 
CaseMouseMouse Pad
Lian Li A05NB with 140mm top fan. Razer DeathAdder Razer Kabuto 
  hide details  
Reply
TheHydra
(13 items)
 
  
CPUMotherboardGraphicsRAM
i7 860 @ 3.6 EVGA P55 FTW Sapphire TOXIC 2GB 6950 CORSAIR XMS3 4 x 2GB CMX4GX3M2A1600C7 
Hard DriveOSKeyboardPower
C300 64Gb + 2x F3 HD103SJ 1TB in RAID 0 Win7 x64 Razer BlackWidow Corsair 750HX 
CaseMouseMouse Pad
Lian Li A05NB with 140mm top fan. Razer DeathAdder Razer Kabuto 
  hide details  
Reply
New Posts  All Forums:Forum Nav:
  Return Home
  Back to Forum: Coding and Programming
Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Help with Finite Automaton Question