Categories of Regular Expressions

 

Category 1: Basic Regular Expressions

Sr.Regular ExpressionExplanation
1aOnly a single character "a".
2abSequence "a" followed by "b".
3(a+b)Either "a" or "b".
4(a)*Zero (ε) or more occurrences of "a".
5(ab)*Zero (ε) or more repetitions of the sequence “ab".
6(a+b)*Zero (ε) or more symbols from the alphabet {a,b} of any length, any order.
7(a)+One or more occurrences of "a".
8(ab)+One or more repetitions of the sequence "ab".
9(a+b)+One or more symbols chosen from "a" or "b".
10(10+1)*Zero (ε) or more repetitions of "10" or "1".
11(01+10+1)*Zero (ε) or more repetitions of "01", "10", or "1".
12(a+b+c+d)*Zero (ε) or more symbols chosen from "a", "b", "c", or "d".
13(a+b+c+d)+One or more symbols chosen from "a", "b", "c", or "d".
14(ab+bb+cc+dd)*Zero (ε) or more repetitions of "ab", "bb", "cc", or "dd".
15101 + (0+1)*1Either "101" or any combination of 0s and "1s” ending in "1".
1611 + 00 + 0 + 10*Either "11", "00", a single "0", or "1" followed by zero or more "0s”.
171(0 + 11) + 0(00 + 1)Either "1" followed by "0" or "11", or "0" followed by "00" or "1".
18ba + (aa + b)*Either "ba" or any number of repetitions of "aa" or "b".
19aa + ba + (aa + b)*Either "aa", "ba", or any number of repetitions of "aa" or "b".
20(00)*(0 + 1) + (1)*Zero (ε) or more "00"s followed by 0 or 1, or any number of "1s”.
21(001)* + (00)Zero (ε) or more repetitions of "001", or exactly "00".

Category 2: Start with Regular Expressions

r.Regular ExpressionSimple Explanation
1a(a+b)*Starts with a, followed by any number (even zero) of as or bs in any order.
2101*(0+1)*Starts with 10, then zero or more repeats of 1, then zero or more mix of 0s and 1s.
3bab(a+b)*Starts with bab, followed by zero or any number of as or bs .
4aa(aba+bab)*Starts with aa, followed by zero or any number of the patterns aba or bab.
5(a(bb)*)(a+b)*Starts with a, then zero or more bbs, then zero or any number of as or bs in any order.
61(0+1)(00+11)*Starts with 1, then either 0 or 1, then zero or more repeats of 00 or 11.
7a+b+c(ab+bb+cc)*One"a", One “b”, or starts with"cand then zero or more repeats of ab, bb, or cc patterns.
8a+b+c+d(ab+bb+cc+dd)*One"a", One “b”, One “c” or starts with"dand then zero or more repeats of ab, bb, cc, or dd patterns.
9aba(a+b)* + bab(a+b)*Either starts with aba or bab, followed by zero or any number of as or bs

Category 3: End with Regular Expressions

Sr.Regular ExpressionSimple Explanation
1(a+b+c+d)*abAny mix of a, b, c, d (including empty), ending with ab.
2(aaa+bbb)*baRepeats of aaa or bbb (or none), ending with ba.
3(a+b+c)*abcAny mix of a, b, or c (including empty), ending with abc.
4(0+1)*101*Any mix of 0s and 1s, followed by 10, and then any number of 1’s.
5(a+b)*a(a+b)bAny mix of a and b, then an aa or ab,and ending with b.
6(00+11)*1(0+1)Repeats of 00 or 11 (or none), followed by 1, and then either 0 or 1

Category 4: Start and End with Regular Expressions

Sr.Regular ExpressionSimple Explanation
11(1+0)*1 + 0(1+0)*0Strings that start and end with 1 or start and end with 0, and mix of 0, 1 in between
211(0+1)(00)Starts with 11, then either 0 or 1, and ends with 00.
300(11)*101Starts with 00, followed by any number of 11's, and ends with 101.
4aba(aa+b)*baStarts with aba, followed by any number of aa or b, and ends with ba.
5b*(aaa+bbb)*baAny number of bs, followed by any number of aaa or bbb, and ending with ba.
6a(a+b)*ba + aEither just a, or starts with a, followed by any mix of as and bs, and ends with ba.
70 + 1(0+1)*10Either a single 0, or a string starting with 1, then anything over 0,1, and ending with 10.
8(11)*(0+1)(00)Repeats of 11, followed by either 0 or 1, and ending with 00.
9(1)*(0+1)*(00)*Any number of 1s, followed by any combination of 0s and 1s, followed by any number of 00s.
1010(101+0+1)*1Starts with 10, followed by any number of 101, 0, or 1, and ends with 1.
11ac(a+b+c)*baStarts with ac, then any mix of a, b, or c, and ends with ba.
12d(a+b+c)*badStarts with d, then any mix of a, b, or c, and ends with bad.
13acd(a+b+c)*badStarts with acd, then any mix of a, b, or c, and ends with bad.
14    bb(a+b)*aa(aa+bb)Starts with bb, followed by any mix of as and bs, then aa, and ends with either aa or bb.
15           (aa+bb)((aa)*+b)*baStarts with aa or bb, followed by any number of aas or bs, and ends with ba.

Comments

Post a Comment

Popular posts from this blog

Theory Of Computation PCCST302 KTU Semester 3 BTech 2024 Scheme

About Me Course Details and Syllabus Module-1 Foundations of Finite Automata Motivation-Computability Need for Mathematical Modelling and automata Introducing automata     on-off switch     coffee vending machine Alphabet, Strings, and Languages Formal Definition of Finite Automata Deterministic Finite Automata - DFA Dead state in DFA Categories of DFA      Category 1: Accept Only the Given Input      Category 2: Starts and ends with      Category 3: Contains substring      Category 4: Specific length     Category 5: Divisibility ( Binary Numbers) Examples  DFA( University Questions) DFA Implementation C Program Non Deterministic Finite Automata - NFA Epsilon NFA  (∈-NFA) Examples NFA( University Questions) Regular Languages Epsilon Closure of NFA Eliminating Epsilon Transitions from NFA Epsilon Free NFA to DFA Conversion - Examples DFA state minimization DFA vs NFA Applications of Fini...
Read more

Non deterministic Finite Automata NFA

Image
  🤖 Formal Definition of NFA An NFA (Nondeterministic Finite Automaton) is a theoretical machine used to recognize regular languages , like a DFA, but it allows multiple transitions for the same input or even no input at all (ε-transitions) . 📘 An NFA is defined as a 5-tuple : M = ( Q , Σ , δ , q 0 , F ) M = (Q, \Sigma, \delta, q_0, F) Where: Symbol Description Q Q A finite set of states Σ \Sigma A finite set called the input alphabet δ \delta The transition function : δ : Q × ( Σ ∪ { ε } ) → 2 Q \delta: Q \times (\Sigma \cup \{\varepsilon\}) \rightarrow 2^Q  (a set of states) q 0 q_0 ​ The initial state , q 0 ∈ Q q_0 \in Q F F The set of accepting states , F ⊆ Q F \subseteq Q 💡 Key Differences from DFA: DFA NFA Only one transition per input                Multiple transitions possible No ε-transitions                ε-transitions allowed Deterministic      ...
Read more

Example DFAs University Questions

Image
 Even number of a's ab as a substring empty set All strings except the empty set over the alphabet {0.1} Accept empty string and 0 every odd position of the string w is 1 begins with 1 ends with 0 {w| w contains at least 3 ones }  {w|w contains the substring 0101 ie; w=x0101y for some x and y} {w|w has length at least 3 and its third symbol is a zero} {w|w starts with 0 and has odd length , or starts with 1 and has even length } construct a DFA which accepts the language L = {a^N | N ≥ 1} String in {a,b} with odd number of a's starting with 01 over the alphabet [1,0} Strings ending with abc Program to build a DFA that checks if a string ends with "01" or "10" build a DFA to accept strings that start and end with same character build DFA that starts and end with 'a' from input (a, b) build a DFA that accepts strings starting and ending with different character DFA of a string starting with 0 and ends with 10? DFA of a string of a's and b's  st...
Read more