Recursive definition of a set of strings.
2,045
You can describe $E_a$ using the regular expression $(aa+ba)^*(a+b+\lambda)$, which translates into a recursive definition with
- Base case: $\lambda, a, b\in E_a$
- Recursive case: if $w\in E_a$, then $aaw, baw\in E_a$.
Related videos on Youtube
19 : 27
Discrete Math 5.3.1 Recursive Definitions
03 : 01
Recursive definition for a string
06 : 56
Recursive Definition of a Set: A Linguistic Example (Set Theory for Linguists 3)
04 : 23
Recursively Defined Sets
07 : 45
Recursive Definition of Strings final
Author by
user1732558
Updated on August 01, 2022Comments
-
user1732558 16 days
Need assistant with this problem, Assume that $\Sigma=\{a,b\}$. Give a recursive definition of the set $E_a$ of all the strings $x\in\Sigma^*$ such that all the symbols occurring at the even positions in $x$ are equal to $a$. I know that Base case $\lambda$ $ \epsilon$ $ \Sigma^* $ but where should I go from there.
-
mrp over 7 yearsWould I not be able to get $ba\lambda \in E_a$, which has a $b$ as the second (i.e. an even position) letter?
-
Klaus Draeger over 7 yearsBut $ba$ ($\lambda$ being the empty string) has an a as its second letter...
-
mrp over 7 yearsAh yes, I was reversing things in my head. Good answer, +1.
