Tagged Questions

1
vote
1answer
88 views

How would I go about proving for this NFA?

I am struggling on this one question, where it is asking to define an XOR automata which is defined as an NFA and it is defined as the following: N accepts the string x if the number of distinct ...
1
vote
1answer
67 views

Proving this language is not regular

Let $$L = \left\{b^ic^jd^k \mid i \ge 0, j\ge 0, k\ge 0,\text{ if }i=1\text{ then }j=k\right\}\;.$$ I have been trying to get a start on this proof for a long time now with no success. What would ...
2
votes
1answer
47 views

Is regularity is preserved under reversal?

When talking about languages and regular languages. Can I say that reversal preserved regularity since if the language L is regular, we can generate it by right linear grammar. Therefore, the ...
0
votes
2answers
76 views

Help with regular expression subset proof

Okay, so basically I'm just showing that two ways to express a regular expression are equal, and to do so, I'm showing they're subsets of each other. The expression is: $(A^*B^*)^* \subset ...
0
votes
3answers
556 views

Formally prove that every finite language is regular

I know how to prove this informally, but don't know what the formal proof should look like.
1
vote
2answers
207 views

Prove that the language $\{ww \mid w \in \{a,b\}^*\}$ is not FA (Finite Automata) recognisable.

Hint: Assume that $|xy| \le k$ in the pumping lemma. I have no idea where to begin for this. Any help would be much appreciated.
0
votes
1answer
108 views

For languages A and B which are both FA recognisable, how do you prove that the concatenation of A and B, A.B is also FA recognisable?

Note: FA = Finite Automaton Given that N1 and N2 are the finite automatas that recognise A and B respectively, I know that N1 and N2 needs to be combined into a new automation N that starts in the ...