My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum

LinkBack Thread Tools Display Modes
October 20th, 2014, 04:03 AM   #1
Joined: Oct 2014
From: Sweden

Posts: 1
Thanks: 0

Discrete Mathematics


I'm in deep trouble. I cannot figure out how to solve a problem in discrete mathematics. And it is the last problem I need to solve. Been working on this one for a long time and feel like I would definitely need some help if you have the time...

A non-deterministic finite automaton is a finite automaton in which the same
input from the same state may lead to several different possible transitions.
A non-deterministic finite automaton accepts an input string if at least one
of possible sequence of transitions leads to an accepting state. Prove that
for any regular language it is possible to construct a non-deterministic finite
automaton with a single accepting state that recognizes the language. Hint!
Start by showing how to construct an automaton that recognizes a single
symbol or λ. Then show how to construct three non-deterministic automata,
each with a single accepting state, to recognize the composite languages
R1 + R2, R1R2 and R1*, given that you already have such automata for the
regular languages R1 och R2. Explain how an induction argument completes
the proof.

Can you help me with this one?

Last edited by skipjack; November 19th, 2014 at 12:38 AM. Reason: Added missing "fi" and "ff"
rntbeats is offline  
October 20th, 2014, 05:55 AM   #2
Global Moderator
CRGreathouse's Avatar
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 933

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Some letters were lost when you copy/pasted this -- "nite automaton" is "finite automaton" and "dierent" is "different". It may be easier to read the original
see p. 18 for this problem.

The hint seems to be very explicit -- I would follow it. Which are the steps are you having trouble with?
1. Construct an automaton to accept a single letter, say "x".
2. Construct an automaton to accept λ (is this your notation for the empty string?)
3. Given automata to match languages R1 and R2, construct an automaton to match R1 + R2 (either R1 or R2).
4. Given automata to match languages R1 and R2, construct an automaton to match R1R2 (R1 followed by R2).
5. Given an automaton to match language R1, construct an automaton to match R1* (zero or more instances of R1).
6. Using 1-5, construct an automaton to accept any regular language (by induction).
CRGreathouse is offline  
November 18th, 2014, 04:39 AM   #3
Senior Member
Joined: Apr 2014
From: Glasgow

Posts: 2,049
Thanks: 680

Math Focus: Physics, mathematical modelling, numerical and computational solutions
If you copy and paste from a pdf, 'ff' and 'fi' doesn't get interpreted correctly and it doesn't go into your clipboard. You have to type it out manually or link the original pdf.
Benit13 is offline  
November 23rd, 2014, 02:38 AM   #4
Joined: Nov 2014
From: Kazakhstan

Posts: 1
Thanks: 0

Find all automorphisms of the following graph:

Find all automorphisms of the following graph. Also, Prove that there are no more automorphisms than those you listed in part 1.
Attached Images
File Type: png x.png (5.2 KB, 1 views)
JohnLennon is offline  

  My Math Forum > College Math Forum > Applied Math

discrete, mathematics

Thread Tools
Display Modes

Similar Threads
Thread Thread Starter Forum Replies Last Post
Discrete Mathematics. Shruthi318 Applied Math 0 November 9th, 2013 09:42 PM
Discrete mathematics question mathboss Applied Math 0 January 18th, 2013 04:33 AM
discrete mathematics conradtsmith Abstract Algebra 1 April 19th, 2010 07:02 AM
discrete mathematics conradtsmith Number Theory 1 April 19th, 2010 06:11 AM
Discrete Mathematics. Shruthi318 Complex Analysis 0 December 31st, 1969 04:00 PM

Copyright © 2017 My Math Forum. All rights reserved.