The Gateway to Computer Science Excellence
+1 vote
41 views

Consider the following non-deterministic finite automata(NFA) $A_{1}$ and $A_{2}:$

  1. Give an example of a word which is accepted by both $A_{1}$ and $A_{2}.$
  2. Give an example of a word which is accepted by $A_{1},$ but not by $A_{2}.$
  3. Draw the deterministic finite automaton(DFA) equivalent to $A_{1}.$
in Theory of Computation by Boss (17.5k points)
retagged by | 41 views

1 Answer

0 votes

The Machine $A_1$ is accepting all strings that ends with $a$  i.e. $L_1 = \{a ,ba,aa, bba,aba, aaa, aba....\}$

The Machine $A_2$ is accepting all strings that starts with $b$ i.e. $L_2 = \{ b, ba, bb, baa, bbb, bab, bba ....\}$

 

$A.$    $ba$ is a string which is accepted by both $A_1$ and $A_2$

$B.$    $aa$ is a string which is accepted by $A_1$ but not by $A_2$

$C.$     The DFA for $A_1$ is as shown

.

by Boss (24.1k points)
edited by
0
Drawn DFA is not correct, its still NFA

$q_0$ will not contain the transition $\textbf{a}$ to itself and $q_1$ will contain the self loop $\textbf{a}$ to itself
0
yes correct...i will edit it soon

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,336 answers
198,447 comments
105,203 users