How to Create a Regular Expression for Strings with an Odd Number of Zeroes?

Click For Summary
SUMMARY

The discussion focuses on creating a regular expression for binary strings that contain an odd number of zeroes. The solution involves constructing a finite state automaton (FSA) that recognizes strings with one block of a single zero and multiple blocks of two zeroes, interspersed with ones. The approach emphasizes the importance of understanding the structure of the strings to effectively formulate the regular expression.

PREREQUISITES
  • Understanding of regular expressions
  • Familiarity with finite state automata (FSA)
  • Knowledge of Kleene's theorem
  • Basic concepts of string theory in computer science
NEXT STEPS
  • Research how to construct finite state automata (FSA) for specific patterns
  • Learn about regular expressions syntax and usage
  • Explore Kleene's theorem and its applications in automata theory
  • Study examples of regular expressions that count specific characters in strings
USEFUL FOR

Computer science students, software developers, and anyone interested in automata theory and regular expressions.

EvLer
Messages
454
Reaction score
0
How do I approach this problem?
give a regular expression for a set containing strings consisting of 0s and 1s where numbr of zeroes is odd...
thanks

ps: I have tried it with Kleene's theorem, but there is so many possibilities that i get lost
 
Physics news on Phys.org
What does FSA stand for? finite state automaton?

The way to do this is to break it up into
1. A single block that contains one 0 and otherwise contains 1's
2. Some number of blocks that contain two zeros each and otherwise contain 1's
 
Last edited:

Similar threads

A gardener collected 17 apples...
  • · Replies 32 ·
2
Replies
32
Views
3K
How to analyse a sequence of vehicle states?
  • · Replies 7 ·
Replies
7
Views
3K
Counting strings of alphabets 0,1,2 and 3
  • · Replies 4 ·
Replies
4
Views
2K
How many number of IP addresses are available?
  • · Replies 2 ·
Replies
2
Views
3K
Combination Problem: 8 0s & 10 1s in Bit Strings
  • · Replies 2 ·
Replies
2
Views
1K
Intermediate Value Theorem Problem on a String
  • · Replies 14 ·
Replies
14
Views
3K
Wave Equation: d'Alembert solution -- semi-infinite string with a fixed end
  • · Replies 4 ·
Replies
4
Views
4K
Help me understand this question -- "Three consecutive zeros" in a binary string
  • · Replies 3 ·
Replies
3
Views
2K
How many words of length n are there in this regular language?
  • · Replies 1 ·
Replies
1
Views
2K
Prove ##|\{ q\in\mathbb{Q}: q>0 \} |=|\mathbb{N}|##.
  • · Replies 3 ·
Replies
3
Views
2K