My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum

LinkBack Thread Tools Display Modes
December 12th, 2015, 01:57 AM   #1
Joined: Mar 2015
From: USA

Posts: 34
Thanks: 1

Automata question

The question:
Let it be $L$ a regular language.
few definitions:
$p(L)$-the minimal natural number so that $L$ fulfill the pumping lemma.
$n(L)$- minimal NFA that accepts $L$.
$m(L)$- $Rank(L)$, the number of equivalence classes in $L$.

Let it be integer $k>0$. find an example for a language $L$ so that: $p=n=m=k$.

My attempt:
At start, thought of $L=\{w: |w|\bmod k=0\}$, $\Sigma=\{ a\}$.
But then I realized that $p<k$.
And also- for every $L$ that I choose here, I don't know how exactly to prove that the $NFA$ which accepts it is minimal. I know how to do this only on $NFA$'s with one or two states, but not on $NFA$'s with unknown number of states.
How can I solve this?
Lobinho is offline  

  My Math Forum > Science Forums > Computer Science

automata, question

Thread Tools
Display Modes

Similar Threads
Thread Thread Starter Forum Replies Last Post
Automata Question Saman Q Computer Science 2 November 8th, 2015 01:42 AM
Automata - a question taih Applied Math 1 December 22nd, 2013 12:17 PM
Elementary Cellular Automata are just the first layer BenFRayfield Number Theory 0 July 30th, 2013 08:32 AM
Construction of Deterministic Finite Automata MrPhil Computer Science 0 August 30th, 2012 11:48 PM
Linear Bounded Automata Phrzby Phil Computer Science 0 June 12th, 2007 11:02 AM

Copyright © 2019 My Math Forum. All rights reserved.