Transformation from NFA to DFA MCQs | Compiler Design

MCQ

11.

What is the complement of the language accepted by the NFA shown below? Assume ? = {a} and ? is the empty string.

{a, ?}

Discussion

MCQ

12.

Given the language L = {ab, aa, baa}, whih of the following strings are in L*?

i) abaabaaabaa
ii) aaaabaaaa
iii) baaaaabaaaab
iv) baaaaabaa

i, ii and iii

ii, iii and iv

i, ii and iv

i, iii and iv

Discussion

MCQ

13.

Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. Complete the partially completed DFA that accepts this language is shown below.

The missing arcs in the DFA are

Discussion

MCQ

14.

Which of the following problems occur?

i) Does a given program ever produce an output?
ii) If L is a CFL, then is L



                                
                                                                                                                        
                                                
                                                
                                                
                                                    A                                                
                                                
                                                
                                                    i, ii, iii, iv                                                
                                            
                                                                                    
                                                
                                                
                                                
                                                    B                                                
                                                
                                                
                                                    i, ii                                                
                                            
                                                                                    
                                                
                                                
                                                
                                                    C                                                
                                                
                                                
                                                    ii, iii, iv                                                
                                            
                                                                                    
                                                
                                                
                                                
                                                    D                                                
                                                
                                                
                                                    iii, iv                                                
                                            
                                                                                                            

                                
                                    Correct Answer: D
                                    i) Is a variation of Turing Machine Halting problem and it is undecidable.



                        
                            

                            
                            
                                                        
                                forum Discussion


                                        
                    
                        
                            
                            
                                
                                    report Report Error
                                
                                
                            

                            
                                
                                
                                    Select Issue Type
                                    
                                                                                
                                            
                                            Wrong Question
                                        
                                                                                
                                            
                                            Wrong Answer
                                        
                                                                                
                                            
                                            Formatting Issue
                                        
                                                                                
                                            
                                            No Solution
                                        
                                                                                
                                            
                                            Wrong Translation
                                        
                                                                                
                                            
                                            Copyright Issue
                                        
                                                                                
                                            
                                            Others
                                        
                                                                            
                                

                                
                                    
                                        
                                            Selected Issue
                                            
                                        
                                        
                                    

                                    
                                        Please provide more details (Optional)
                                    
                                    
                                
                                
                            

                            
                                
                                
                            
                        
                    
                    
                    
                                    
                        
                            
                                MCQ                            
                            
                        

                        
                            
                            
                                
                                    15.
                                    The definition of a language L with alphabet {a} is given as following. L = { ank | k > 0, and n is a positive integer constant} What is the minimum number of states needed in a DFA to recognize L?
                                

                                
                                                                                                                        
                                                
                                                
                                                
                                                    A                                                
                                                
                                                
                                                    k+1                                                
                                            
                                                                                    
                                                
                                                
                                                
                                                    B                                                
                                                
                                                
                                                    n+1                                                
                                            
                                                                                    
                                                
                                                
                                                
                                                    C                                                
                                                
                                                
                                                    2n+1                                                
                                            
                                                                                    
                                                
                                                
                                                
                                                    D                                                
                                                
                                                
                                                    2k+1                                                
                                            
                                                                                                            

                                
                                    Correct Answer: B
                                    Note that n is a constant and k is any positive integer. For example, let n=3, then the DFA must be able to accept aaa, aaaaaa, aaaaaaaaa, , .. build such a DFA, 4 states are required.
                                
                            
                        

                        
                            

                            
                            
                                                        
                                forum Discussion
                            
                        
                    
                                        
                    
                        
                            
                            
                                
                                    report Report Error
                                
                                
                            

                            
                                
                                
                                    Select Issue Type
                                    
                                                                                
                                            
                                            Wrong Question
                                        
                                                                                
                                            
                                            Wrong Answer
                                        
                                                                                
                                            
                                            Formatting Issue
                                        
                                                                                
                                            
                                            No Solution
                                        
                                                                                
                                            
                                            Wrong Translation
                                        
                                                                                
                                            
                                            Copyright Issue
                                        
                                                                                
                                            
                                            Others
                                        
                                                                            
                                

                                
                                    
                                        
                                            Selected Issue
                                            
                                        
                                        
                                    

                                    
                                        Please provide more details (Optional)

Banking

Engineering

General

Medical

Transformation from NFA to DFA Questions

Report Error

Report Error

Report Error

Report Error

Report Error