Conversion of e-NFA to DFA

Problems Solved during Class Room Teaching

Problem 1:

Problem 2:

Continue reading →

Tutorial-2 on RE & CFG

Tutorial-2 on RE & CFG

Q1.  Illustrate the construction of Non Deterministic Finite Automata for the Regular Expression: (a+b)*a

Q2.  Construct the regular expression for the language over the set S={0,1} that can have a set of all strings containing no three consecutive 0’s

Q3.  Construct a CFG to generate the binary strings that are Palindromes ex: 010, 00100, 101, 11011

Q4.  Identify the language generated by the following CFG:  S-->Aab; A-->Aab|b

Q5.  Construct the NFA for the regular expression r = ((01+10)*00)*

Q6. Constructure the Finite Automata using 5-tuple notation for the regular expression 1*01(0+11)*

Continue reading →

Tutorial-1 on Automata Theory

Tutorial-1 on Finite Automata

Q1.  For the given NFA which of the following is the equivalent DFA:

Q2.  Consider the following NFA and answer the following:

        a) Compute the ε-closure of each state.

        b) Convert the automaton to a DFA.

Q3.  Consider the following ε-NFA and do the following:

      a) Compute the ε-closure of each state.

      b) Convert the automaton to a DFA.

Q4.  Constructure the Finite Automata from the following 5-tuple notation:

Q5.  Convert the given ε-NFA to its equivalent DFA:

Continue reading →

Test Your Knowledge on Regular Expressions

Multiple Choice Questions on RE & CFG 

Q1.  Given the language L = {ab, aa, baa}, which of the following strings are in L*? 
        1) abaabaaabaa 
        2) aaaabaaaa 
        3) baaaaabaaaab 
        4) baaaaabaa 

Possible Answers:

        (A) 1, 2 and 3 
        (B) 2, 3 and 4 
        (C) 1, 2 and 4 
        (D) 1, 3 and 4 

Q2. What is the Regular Expression (RE) over the alphabet Σ={a,b} for the language that indicate the strings containing "ab" as substrings?

        (A) (a+b)ab(a+b)

        (B) (a+b)*ab(a+b)*

        (C) (ab)*ab(ab)*

        (D) ab(a+b)*

Q3.  Consider the FA shown in the figure given below, where ‘-’ is the start sate and ‘+’ is the ending state.  The language accepted by the FA is

Q4.  Which regular expression best describe the language accepted by the non-deterministic automaton below?

Q5:

Q6: From the following regular expressions over an alphabet {a, b} given below, which can yield all the possible strings over ∑ (a, b)?

Q7. Which of the following options are correct for the given DFA:

(A) 0(10)*

(B) (01)*0

(C) Both (A) and (B)

(D) Neither (A) nor (B)

Q8. 

Q9. Pumping lemma is generally used for proving which of the following:

(A) A given grammar is regular

(B) A given grammar is non-regular

(C) Whether two given regular expression are equivalent or not

(D) Both (A) and (C)

Q10. Sentence that can be generated from the following production grammar is:

Descriptive Questions on Regular Expressions

Q1. Construct an NFA and a DFA for recognizing the language denoted by the regular expression aa* + bb* 

Q2.  Write regular expressions for the following languages over the alphabet {0, 1}:

    a) The set of all strings that begin with 110.

    b) The set of all strings that contain 1011.

    c) The set of strings of 0's and 1's with at most one pair of consecutive 1's.

Q3.  Write regular expressions for the following languages over the alphabet {a, b}:

    a) The set of strings containing at least one a and at least one b .

Q4.  Convert the following regular expressions to NFA's with ε -transitions.

Continue reading →

Test Your Knowledge on Finite Automata

Multiple Choice Questions on Automata 

Q1. Finite state machine can recognize which of the following languges:

       (A) Only context-free grammar

       (B) Only regular grammar

       (C) Any unambiguous grammar

       (D) Any grammar

Q2. The language, L is defined over Σ = {0, 1, 2, 3, 4, 5, 6, 7} has the following set of strings included in its dictionary:

L = {7, 16, 43, 61, 223, ...} 

Identify the language represented by L from the following options:

       (A) Alternate odd and even numbers

       (B) Octal representation of a number

       (C) Divisible by 7

       (D) Octal representation of a number divisible by 7.

Q3.  Which of the following statements about ε-moves (epsilon transitions) in Finite Automata is correct?

       (A) An ε-move consumes one input symbol from the alphabet

       (B) ε-moves are allowed only in DFA

       (C) ε-moves allow the automaton to change states without consuming any input symbol

       (D) An automaton with ε-move always accepts all input strings

Q4.

       (A) Regular Language

       (B) Context-Sensitive Language

       (C) Context-Free Language

       (D) Phrase-Structure Language

Q5. Consider the given finite automaton and identify the Language recognised by it:

        (A) A DFA that accepts all strings that end with "ba"

        (B) A DFA that accepts all strings that end with "a"

        (C) A DFA that accepts all strings that end with "b"

        (D) A DFA that accepts all strings that end with "ab"

Q6.  In the automaton below, s is the start state and t is only final state.

Q7.  The below transition diagram of a finite automaton accepts which of the following set of strings?

Q8.  For the given NFA which of the following is the equivalent DFA:

Q9. How many states will the DFA equivalent of NFA with n states have in the worst case?

 

        (A) n

        (B) 2n

        (C) 2ⁿ

        (D) n²

Q10. Two finite state machines are said to be equivalent if they:

 

        (A) Have the same number of edges

        (B) Have the same number of states

        (C) Recognise the same set of tokens

        (D) Have the same number of edges and states

Q11.  ‘Every NFA can be simulated by a DFA’. The statement is true/false?

Design Automata for Representing a Language

Q1.  Consider the following NFA and answer the following:

        a) Give all the strings of length three or less accepted by the automaton.

        b) Convert the automaton to a DFA.

Q2.  Consider the following ε-NFA and do the following:

      a) Compute the ε-closure of each state.

        b) Give all the strings of length three or less accepted by the automaton.

        c) Convert the automaton to a DFA.

Q3.  Constructure the Finite Automata from the following 5-tuple notation:

Continue reading →

Automata Theory and Compiler Design (2412PC02)

R24 Syllabus of Automata & Compiler Design

UNIT - I

Introduction to Finite Automata: Structural Representations, Automata and Complexity, the Central Concepts of Automata Theory – Alphabets, Strings, Languages, Problems.

Nondeterministic Finite Automata: Formal Definition, an application, Text Search, Finite Automata with Epsilon-Transitions.

Deterministic Finite Automata: Definition of DFA, How A DFA Process Strings, The language of DFA, Conversion of NFA with €-transitions to NFA without €-transitions, Conversion of NFA to DFA

UNIT - II

Regular Expressions: Finite Automata and Regular Expressions, Applications of Regular Expressions, Algebraic Laws for Regular Expressions, Conversion of Finite Automata to Regular Expressions.

Pumping Lemma for Regular Languages: Statement of the pumping lemma, Applications of the Pumping Lemma.

Context-Free Grammars: Definition of Context-Free Grammars, Derivations Using a Grammar, Leftmost and Rightmost Derivations, the Language of a Grammar, Parse Trees, Ambiguity in Grammars and Languages.

UNIT - III

Push Down Automata: Definition of the Pushdown Automaton, the Languages of a PDA, Equivalence of PDA and CFG’s, Acceptance by final state

Turing Machines: Introduction to Turing Machine, Formal Description, Instantaneous description, The language of a Turing machine

Undecidability: Undecidability, A Language that is Not Recursively Enumerable, An Undecidable Problem That is RE, Undecidable Problems about Turing Machines

UNIT - IV

Introduction: The structure of a compiler,

Lexical Analysis: The Role of the Lexical Analyzer, Input Buffering, Recognition of Tokens, The Lexical- Analyzer Generator Lex,

Syntax Analysis: Introduction, Context-Free Grammars, Writing a Grammar, Top-Down Parsing, Bottom- Up Parsing, Introduction to LR Parsing: Simple LR, More Powerful LR Parsers

UNIT - V

Syntax-Directed Translation: Syntax-Directed Definitions, Evaluation Orders for SDD's, Syntax- Directed Translation Schemes, Implementing L-Attributed SDD's.

Intermediate-Code Generation: Variants of Syntax Trees, Three-Address Code

Run-Time Environments: Stack Allocation of Space, Access to Nonlocal Data on the Stack, Heap Management

Continue reading →

Quality Management (Unit V)

 

Quality Management (Unit 5)

Quality Concepts

Quality is a concept that can be defined from different point of view as follows:

• From the user's point of view, quality is determined based on the ability of the product (software) in meetings its customer's needs (goals)
• From the manufacturer's point of view, quality product confirms to the original specification of the product (system specifications)
• From the product view, quality refers to the various inherent characteristics (e.g., functions and features) of the product
• From the value-based view, quality is determined based on how much it is valued in the market place 

In software development, quality is imparted in software during each and every phase of its development - Analysis, Design and Development.

• During analysis, requirements are identified and documented to identify the needs of the user
• In design phase, the blue print of the software is prepared based on the specifications identified.  
• Development is carried out based on the design documents and then the testing takes place to verify and validate the quality of the software

Process View of Software Quality:

In general, software quality can be defined as "an effective software process applied in a manner that creates a useful product (software) that provides measurable value (quality software) for those who produce it and those who use it."

• An effective software process establishes the infrastructure that supports any effort at building a high-quality software product.
• Quality of conformance is a metric that determines the degree to which the implementation (3rd phase of SDLC) follows the design and the resulting system meets its requirements and performance goals.  
• The quality of the design is based on the degree to which the design (2nd phase of SDLC) meets the functions and features specified in the requirements model.

Software Quality is basically measured based on the following criteria:

• Conformance to Requirements: Does the software do what it's supposed to do as defined in the requirements and design? This is often called as functional quality.
• Fitness for Use: Does the software meet user expectations in terms of its behaviour, performance, and attributes?  This includes non-functional aspects like reliability, usability, and maintainability (characteristics) of the software.
• A useful product delivers the content, functions, and features that the end user desires in a reliable, error-free way.  It always satisfies the requirements that have been explicitly stated by stakeholders.

 

Software Quality Dilemma

• Software quality dilemma refers to the constant pressure applied to compromise the desire for high-quality software in order to yield the constraints of development work in terms of time, cost, and scope.
• Software quality dilemma manifests most clearly in the trade-offs development teams have to make.

Speed vs. Quality: 

• Rushing to release a product or some portion of the product quickly often means cutting corners on testing, code reviews, and proper design. 
• This leads to technical debt—a hidden cost of fixing bugs and maintaining the poorly built system later, which ultimately slows down future development.

Cost vs. Quality: 

• Investing in quality processes (hiring senior engineers, implementing rigorous testing, setting up robust automation) costs money and time upfront.
• A smaller budget often forces a team to skimp on these investments, leading to a cheaper, faster initial release but a much more expensive product to maintain in the long run.

Scope Creep vs. Stability: 

Trying to pack too many features into a release (expanding scope) inevitably puts pressure on the schedule and budget, leading to the same shortcuts that degrade quality.

The "Good, Fast, Cheap" Triad: 

In this triad of Good quality, Fast delivery and Low cost production, we are allowed to pick any two of the three in order to overcome the dilemma in producing the quality software:

• Good (High Quality): Reliable, maintainable, secure, and user-friendly.
• Fast (Quick Delivery): Meeting tight deadlines and time-to-market.
• Cheap (Low Cost/Resource Use): Staying within a strict budget.

For instance:

• Developing software with low budget (cheap) and quick delivery (fast) will result in software that may not have the expected quality
• Compromising any one of the two factors - quick delivery (fast) or low budget (cheap) can help in developing software with low budget or speedy delivery

 

Software Quality Assurance (SQA)

• Software Quality Assurance (SQA) is a systematic process that ensures software development processes and developed products meet pre-defined standards and requirements. 
• It's an umbrella activity applied throughout the entire software development lifecycle (SDLC) to prevent defects and improve the overall quality of the product and the process used to create it. 

 

Goals of Software Quality Assurance:

SQA encompasses testing, but it is not only testing.  The primary goals of SQA include:

• Defect Prevention: Stick to the procedures, standards, and guidelines to avoid errors (defects) in the development process
• Process Improvement: Continuously evaluate and refine the development process to increase efficiency and quality of the development process
• Verification and Validation (V&V):

• Verification: Answers the questions, "Are we building the product right?" to verify if the product conforms to stated specifications of the user
• Validation: Answers the question, "Have we built the right product?" to confirm that the product meets the needs of the user, both functional and non-functional.

• Standard Conformance: Ensures that the software and the process adhere to internal organizational standards, external regulatory standards (like ISO 9000), and best practices.

 

Core Activities involved in SQA:

SQA is broader than just testing and involves various activities as follows:

• Defining Standards and Metrics: Establishes a set of engineering practices, development standards, and metrics (e.g., defect density, mean time to failure) that the project must adhere to.
• Reviews and Audits: Conduct of formal technical reviews, quality audits, and inspections on artifacts like requirements, design documents, and code to catch errors early in the development process
• Process Monitoring: Tracking the development process against the defined plan to ensure compliance and identify deviations
• Testing: Perform various types of testing (unit, integration, system, acceptance, etc.) to confirm functionality and identify defects
• Configuration Management: Monitors and controls changes to the software artifacts throughout the SDLC

 

SQA Vs. Software Testing:

While related, SQA and Software Testing are distinct concepts: 

Feature	Software Quality Assurance (SQA)	Software Testing
Focus	Process Management and Prevention of defects	Product Management and Identification of defects
Goal	Improving development methodology	Ensuring that the product meets requirements of the user
Scope	Encompasses the entire SDLC (requirements, design, coding, testing, etc.).	Primarily a phase within the SDLC (systematically executing the product).
Question	How can we build the software better?	Does the software being developed work as expected?

 

Software Reviews & Formal Technical Reviews

Software Reviews are a general, umbrella term for quality control activities used throughout the software development life cycle (SDLC) to uncover errors and ensure compliance with requirements and standards before they become defects.

Formal Technical Reviews (FTRs) are a highly structured and systematic type of software review, often considered the most rigorous, that focuses on a detailed, peer-driven examination of a specific software work product (like requirements, design documents, or source code) to find defects.

Common Types of Software Reviews:

Given below are some of the common types of software reviews:

• Informal Reviews (e.g., Desk Checks, Pair Programming): Quick, ad-hoc, and often undocumented. They provide fast feedback to catch obvious errors.

• Walkthroughs: A semi-formal process where the author presents the work product to the review team, walking them through it, and the team asks questions and makes suggestions. The focus is often on sharing understanding and finding defects.

• Technical Reviews: A general term for peer reviews focused on technical content; FTRs are the most formal version of this.

• Inspections: The most formal type of review, often considered synonymous with FTR. It emphasizes individual preparation using checklists before a structured meeting, is strictly focused on defect finding, and collects metrics for process improvement.

• Audits: Conducted by personnel external to the project team, focused on compliance with standards, regulations, or contractual agreements.

 

Software Reviews Vs. Formal Technical Reviews: 

Feature	Software Review (General Term)	Formal Technical Review (A Specific Type)
Formality	Varies widely, ranging from informal (e.g., "buddy checks," quick code reviews) to formal (like FTRs or Inspections).	Highly formal and structured, following a predefined process (often based on standards like IEEE 1028).
Structure & Process	Can be unstructured (ad-hoc discussion) or semi-structured (walkthroughs).	Systematic process with defined steps: planning, preparation, a structured meeting led by a moderator, rework, and follow-up.
Key Objective	To serve as a quality control filter to uncover errors and ensure general quality throughout the SDLC.	Primarily to uncover defects (errors) in function, logic, and implementation, and to verify conformance to standards and requirements.
Documentation	Minimal to moderate, depending on the formality (e.g., informal notes).	Extensive documentation, including a Formal Technical Review Summary Report and a detailed list of issues.
Participants	Can involve just two people (informal) or a larger team.	A small, designated team (typically 3-5) with defined roles: Moderator, Producer (Author), and Reviewers/Recorder.
Focus	Can be technical, managerial (status, resources), or compliance-based (audit).	Strictly technical content of a specific work product.

Continue reading →