Formal Language and Automata Homework 5 Answer

Suppose $h$ is the homomorphism from the alphabet ${{0,1,2}}$ to the alphabet ${{a,b}}$ defined by: $h(0)=a;$ $h(1)=ab$, and $h(2)=ba$.

a) What is $h(0120)$?

$h(0120) = h(0)h(1)h(2)h(0) = aabbaa$

b) What is $h(21120)$?

$h(21120) = h(2)h(1)h(1)h(2)h(0) = baababbaa$

c) If $L$ is the languages $L(01^∗2)$, what is $h(L)$?

$h(01^* 2)= h(0)h(1^* )h(2) = a(ab)^* ba$

d) If $L$ is the languages $L(0+12)$, what is $h(L)$?

$h(0+12)=h(0)+h(1)h(2)=a+abba $

e) Suppose $L$ is the language ${{ababa}}$, that is , the languages consisting of only the one string $ababa$. What is $h^{−1}(L)$?

$h^{-1}(L) = 022, 110, 102$

f) If $L$ is the languages $L(a(ba)^∗)$, what is $h^{−1}(L)$?

$h^{-1}(a(ba)^* ) = 02^*$

If $L$ is a languages, and $a$ is a symbol, then $L/a$, the quotient of $L$ and $a$, is the set of strings $w$ such that $wa$ is in $L$. For example, if $L={{a,aab,baa}}$, then $L/a={{ϵ,ba}}$. Prove that if $L$ is regular, so is $L/a$. Hint : Start with a DFA for $L$ and consider the set of accepting states.

Answer:

$L$은 정규 언어이므로, $L$을 인식하는 DFA $A$가 존재한다.
$L/a$가 정규 언어을 증명하기 위해서 DFA $A$로부터 $L/a$를 인식하는 DFA $B$를 만들어보자.
DFA $A$와 똑같이 생긴 DFA $B$를 만들고, 여기서 final state 집합을 초기화한다.
DFA $A$에서 $\delta(q, a)$가 final state임을 만족하는 모든 상태 $q$를 DFA $B$의 final state로 설정한다.
이렇게 하면, DFA $A$가 어떤 문자열 $x = wa$를 인식할 때, DFA $B$는 문자열 w$를 인식하게 된다. (이 문장에 대한 일반적 증명은 induction을 통해 할 수 있다.)

If $L$ is a languages, and $a$ is a symbol, then $a/L$, is the set of strings $w$ such that $aw$ is in $L$. For example, if $L={{a,aab,baa}}$, then $a/L={{ϵ,ab}}$. Prove that if $L$ is regular, so is $a/L$. Hint : Remember that the regular languages are closed reversal and under the quotient operation of Exercise 2.

Answer: