My Math Forum Discrete Mathematics

 Applied Math Applied Math Forum

 October 20th, 2014, 04:03 AM #1 Newbie   Joined: Oct 2014 From: Sweden Posts: 1 Thanks: 0 Discrete Mathematics Hi!! 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"
 October 20th, 2014, 05:55 AM #2 Global Moderator     Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 938 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 http://www.mdh.se/polopoly_fs/1.6275...2014-15-ht.pdf 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).
 November 18th, 2014, 04:39 AM #3 Senior Member   Joined: Apr 2014 From: Glasgow Posts: 2,155 Thanks: 731 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.
November 23rd, 2014, 02:38 AM   #4
Newbie

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
 x.png (5.2 KB, 1 views)

 Tags discrete, mathematics

 Thread Tools Display Modes Linear Mode

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

 Contact - Home - Forums - Cryptocurrency Forum - Top