questions on nfa and dfa..

Posted by Loop on Stack Overflow See other posts from Stack Overflow or by Loop
Published on 2010-04-24T02:31:51Z Indexed on 2010/04/24 2:33 UTC
Read the original article Hit count: 271

Filed under:

regex

|

nfa

|

dfa

|

homework

Hi Guys... Hope you help me with this one....

I have a main question which is ''how to judge whether a regular expression will be accepted by NFA and/or DFA?

For eg. My question says that which of the regular expressions are equivalent? explain... 1.(a+b)*b(a+b)*b(a+b)*

2.a*ba*ba*

3.a*ba*b(a+b)*

do we have to draw the NFA and DFA and then find through minimisation algorithm? if we do then how do we come to know that which regular expression is accepted by NFA/DFA so that we can begin with the answer? its so confusing....

Second is a very similar one, the question asks me to show that the language (a^nb^n|n>1} is not accepted by DFA...grrrrr...how do i know this? (BTW this is a set of all strings of where a number of a's is followed by the same number of b's)....

I hope I explained clearly well....

© Stack Overflow or respective owner

Related posts about regex

Find multiple regex in each line and skip result if one of the regex doesn't match

as seen on Stack Overflow - Search for 'Stack Overflow'
I have a list of variables: variables = ['VariableA', 'VariableB','VariableC'] which I'm going to search for, line by line ifile = open("temp.txt",'r') d = {} match = zeros(len(variables)) for line in ifile: emptyCells=0 for i in range(len(variables)): regex = r'('+variables[i]+r')[:|=|\(](-… >>> More
OWASP Regex Repository: Is this regex correct?

as seen on Stack Overflow - Search for 'Stack Overflow'
I was looking at the regular expression for validating various data types from the (OWASP Regex Repository). One of the regular expressions in there is called safetext and looks like: ^[a-zA-Z0-9\s.\-]+$ My first question is: Is this regular expression correct? complementary question If this… >>> More
Make a Perl-style regex interpreter behave like a basic or extended regex interpreter

as seen on Stack Overflow - Search for 'Stack Overflow'
I am writing a tool to help students learn regular expressions. I will probably be writing it in Java. The idea is this: the student types in a regular expression and the tool shows which parts of a text will get matched by the regex. Simple enough. But I want to support several different regex… >>> More
JS regex isn't matching, even thought it works with a regex tester

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm writing a piece of client-side javascript code that takes a function and finds the derivative of it, however, the regex that's supposed to match with the power rule fails to work in the context of the javascript program, even though it sucessfully matches when it's used with an independent regex… >>> More
c# RegEx with "|"

as seen on Stack Overflow - Search for 'Stack Overflow'
I need to be able to check for a pattern with | in them. For example an expression like d*|*t should return true for a string like "dtest|test". I'm no regex hero so I just tried a couple of things, like: Regex Pattern = new Regex("s*\|*d"); //unable to build because of single backslash Regex Pattern… >>> More

Related posts about nfa

questions on nfa and dfa..

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi Guys... Hope you help me with this one.... I have a main question which is ''how to judge whether a regular expression will be accepted by NFA and/or DFA? For eg. My question says that which of the regular expressions are equivalent? explain... 1.(a+b)*b(a+b)*b(a+b)* 2.a*ba*ba* 3.a*ba*b(a+b)* do… >>> More
A compiler for automata theory

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm designing a programming language for automata theory. My goal is to allow programmers to use machines (DFA, NFA, etc...) as units in expressions. I'm confused whether the language should be compiled, interpreted, or jit-compiled! My intuition is that compilation is a good choice, for some operations… >>> More
How to get lookahead symbol when constructing LR(1) NFA for parser?

as seen on Programmers - Search for 'Programmers'
I am reading an explanation (awesome "Parsing Techniques" by D.Grune and C.J.H.Jacobs; p.292 in the 2nd edition) about how to construct an LR(1) parser, and I am at the stage of building the initial NFA. What I don't understand is how to get/compute a lookahead symbol. Here is the example from the… >>> More
Efficient (basic) regular expression implementation for streaming data

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm looking for an implementation of regular expression matching that operates on a stream of data -- i.e., it has an API that allows a user to pass in one character at a time and report when a match is found on the stream of characters seen so far. Only very basic (classic) regular expressions are… >>> More
How to use iterator in nested arraylist

as seen on Stack Overflow - Search for 'Stack Overflow'
I am trying to build an NFA with a special purpose of searching, which is totally different from regex. The State has following format class State implements List{ //GLOBAL DATA static int depth; //STATE VALUES String stateName; ArrayList<String> label = new ArrayList<>(); //Label for… >>> More