4.2 Regular languages

• What is a regular language defined as?

  Strings described by regex or FSM
• Finite State Machines use a fixed number of states and transitions to recognize patterns.
• Regular languages are closed under union, concatenation, Kleene star, and complement
• What does the Kleene star operator in a regular expression represent?

  Repetition of a pattern
• Regular expressions are used for pattern matching, search and replace, and data validation.
• Match the regular expression component with its description:

  Literals ↔️ Exact characters to be matched

  Anchors ↔️ Specify positions within the text

  Operators ↔️ Control the frequency and order of matches
• The regular expression ^\d{3} - \d{2} - \d{4} matches a U.S. phone number in the format XXX-XX-XXXX
• The regular expression ^\d{3} - \d{2} - \d{4}</latex> is used for data validation purposes.
• What is a Finite Automaton (FA)?

  A computational model
• Match the type of Finite Automaton with its description:

  Deterministic Finite Automaton (DFA) ↔️ Each state has one transition per input

  Non-deterministic Finite Automaton (NFA) ↔️ A state may have multiple or zero transitions
• What is the purpose of the DFA diagram example in the study material?

  Accept strings starting with 'a'
• Converting a regular expression to a finite automaton involves transforming the pattern into a state machine
• Steps to convert a regular expression to a finite automaton:

  1️⃣ Represent each character or symbol as a state

  2️⃣ Combine states for concatenation

  3️⃣ Handle alternation with multiple initial transitions

  4️⃣ Represent repetition with loop transitions
• What is the resulting FA for the regular expression a(b|c) *</latex>?

  A state machine accepting "ab", "ac", etc.
• Regular languages can recognize patterns without storing the entire input.
• In a regular expression, character classes like \d match all digits
• What is the purpose of a Finite Automaton (FA)?

  Recognize regular languages
• There are two main types of Finite Automata: Deterministic and Non-deterministic.
• What does the regular expression \d match?


  Digits
• What does the regular expression $ specify?


  End
• The Kleene star operator $*$ in regular expressions controls the frequency and order of matches
• The regular expression ^\d{3} - \d{2} - \d{4} matches a U.S. phone number format.
• What is a Finite Automaton (FA)?

  Computational model
• What is a Deterministic Finite Automaton (DFA)?

  One transition per input
• What is a Non-deterministic Finite Automaton (NFA)?

  Multiple transitions per input
• A DFA can accept strings starting with 'a' followed by any number of 'b's.
• What triggers transitions between states in a Finite Automaton (FA)?

  Input symbols
• In a DFA, each state has exactly one transition for each input symbol
• Which type of Finite Automaton allows multiple transitions for a single input symbol?

  NFA
• Steps to convert a regular expression to a Finite Automaton (FA)

  1️⃣ Convert each literal to an FA state and transition

  2️⃣ Combine states for concatenation

  3️⃣ Use multiple initial transitions for alternation

  4️⃣ Add a loop transition for repetition
• The regular expression a(b \| c)^∗</latex> can be converted to an FA with a start state and looping transitions.
• Steps to convert a Finite Automaton (FA) to a regular expression

  1️⃣ Label states as $q_{0}$, $q_{1}$, etc.

  2️⃣ Calculate expressions for transitions between states

  3️⃣ Create equations for the language accepted by each state

  4️⃣ Solve equations to find the regular expression for the start state
• What is the regular expression for a DFA with transitions q_{0} \xrightarrow{a} q_{0}</latex> and $q_{0} \xrightarrow{b} q_{1}$, where $q_{1}$ is the accepting state?


  $a^∗b$
• Under which operations are regular languages closed?

  Union, concatenation, repetition
• What is the regular expression for a DFA with states $q_{0}$ and $q_{1}$, and transitions $q_{0} \xrightarrow{a} q_{0}$ and $q_{0} \xrightarrow{b} q_{1}$?


  $a^∗b$
• To convert a finite automaton (FA) to a regular expression, you must first label its states
• Steps to convert a finite automaton (FA) to a regular expression:

  1️⃣ Label states as $q_{0}$, $q_{1}$, etc.

  2️⃣ Calculate expressions for transitions between states

  3️⃣ Create equations for the language accepted by each state

  4️⃣ Solve the equations to find the regular expression for the start state
• What does it mean for a regular language to be closed under an operation?

  Results in another regular language
• The union of two regular languages, L_{1} \cup L_{2}</latex>, combines their individual sets of strings
• What is the result of concatenating $L_{1} =$$\{ab\}$ and $L_{2} =$$\{cd\}$?


  $\{abcd\}$