Stack Overflow
Stack Overflow

Questions tagged [kleene-star]

In computation theory, the kleene star (*) is a regular operation all regular languages are closed under.

In computation theory, the kleene star (*) is a regular operation all regular languages are closed under. The kleene star acts on a language to produce the superset containing the empty string, as well as infinitely many concatenations of the strings in the starred set.

Examples:

  • a* contains the strings: a, aa, aaa, and the empty string
  • (ab)* contains the strings ababababababababab, ab, the empty string, etc.
  • {ab, cd}* contains the empty string, abcd, cdab, cdcd, cdabcdab, etc.

See the wikipedia page for additional details

36 questions
11
votes
4 answers

An infinite language can't be regular? What is a finite language?

I read this in a book on computability: (Kleene's Theorem) A language is regular if and only if it can be obtained from finite languages by applying the three operations union, concatenation, repetition a finite number of times. I am…
Roger Costello
  • 3,007
  • 1
  • 22
  • 43
10
votes
1 answer

Automata Regular expression - difference between concatenation & union

What is the difference between the following regular expressions? (a U b)* and (ab)* Difference between union and concatenation ? which of the above regex accepts strings in which 'a' is always before 'b' ? Please clarify.. Thanks in advance.
Jadyarun
  • 117
  • 1
  • 2
  • 6
6
votes
1 answer

Why can't the Kleene closure construction for an NFA be simplified?

Most sources, such as http://www.cs.may.ie/staff/jpower/Courses/Previous/parsing/node5.html, suggest that the Kleene closure be constructed with 4 nodes. Why can't it be constructed with just 2, as follows?
ackerleytng
  • 416
  • 6
  • 17
5
votes
2 answers

Deterministic Finite Automaton of Kleene Star

I read that every Non-deterministic Finite Automaton (NFA) can be transferred into a Deterministic Finite Automaton (DFA). Can this be done for kleene star regex, say a*? Above is the NFA for a*.
Ankit Shubham
  • 2,989
  • 2
  • 36
  • 61
5
votes
3 answers

Regular expression: does Kleene star have a distributive property?

Would there be a difference between (aa)* and (a*a*)? Is there a distributive property?
user1988365
4
votes
2 answers

Determining if two languages are equal [Regular expression]

preparing for an exam and was going through this problem: Determine whether the set of strings represented by R1 is a subset of R2? R1 = (01 +10)* R2 = ((01)* + (10)*) My attempt: Since there represent the same expression I tried to prove…
Rave
  • 835
  • 4
  • 15
  • 28
4
votes
2 answers

Ambiguity in transition: How to process string in NFA?

I have made DFA from a given regular expression to match the test string. There are some cases in which .* occurs. ( for example .*ab ) . Let say now the machine is in state 1. In the DFA, .* refers to the transition for all the characters to…
Tejas Joshi
  • 197
  • 3
  • 12
3
votes
1 answer

Find all paths in directed cyclic graph as regular expression

Let G = (V,E,r) a rooted directed graph, defined by a set of vertices V and a set of edges E with a designated root node r. The graph may contain cycles. The task: Given two vertices x and y from V, find all paths from x to y. Since cycles are…
Stefan Lutz
  • 161
  • 6
3
votes
1 answer

Converting dot-star regular expression into NFA

I'm converting a given set of regular expressions into a single NFA, but I'm having some issues. How should I convert a regular expression such as "ab.*c" (representing matching an 'a', a 'b', any number of characters, and then a 'c')? My final goal…
Alexandre Dias
  • 107
  • 1
  • 6
2
votes
1 answer

How to apply Kleene star on automata?

I know how to apply Kleene star on language but I'm not sure how would I apply it to DFA or NFA. I'm pretty sure it would need to be epsilon NFA with initial state that is final and final states might need epsilon transition to that initial…
qu4lizz
  • 317
  • 2
  • 12
2
votes
4 answers

If language L is not regular, is L* regular?

It makes sense to assume that L* is not regular. However, I cannot find a proof of either conclusion.
Bobazonski
  • 1,515
  • 5
  • 26
  • 43
2
votes
1 answer

When is the Kleene star of a finite language free?

I'm looking for references that give an algorithm to solve this problem: Problem: Given a finite alphabet Σ and a finite language L ⊆ Σ* , determine whether L* is a free monoid. Equivalently, the problem is to determine, given a finite set…
lambdacalculator
  • 363
  • 2
  • 7
2
votes
3 answers

Automata with kleene star

Im learning about automata. Can you please help me understand how automata with Kleene closure works? Let's say I have letters a,b,c and I need to find text that ends with Kleene star - like ab*bac - how will it work?
Anna
  • 59
  • 1
  • 2
  • 8
1
vote
2 answers

How to use a kleene star operator (*) or it's variant (+) with variables in sparql?

I have some working code for getting all the ancestors of a term in a hierarchy. Following: PREFIX skos: PREFIX skos-xl: PREFIX rdf:…
Cola
  • 2,097
  • 4
  • 24
  • 30
1
vote
2 answers

Does the kleene-star's potence 0 fulfill a disjunction?

Does the regular expression X•(Y*+Z) accept the word X? I would say it does, as Y=ε should fulfill the disjunction, but I'm not sure.
Corbie
  • 819
  • 9
  • 31
1
2 3