Tuesday, February 8, 2022

Chomsky Hierarchy

Chomsky Hierarchy

Chomsky Hierarchy represents the class of languages that are accepted by the different machine. The category of language in Chomsky's Hierarchy is as given below:

  1. Type 0 known as Unrestricted Grammar.
  2. Type 1 known as Context Sensitive Grammar.
  3. Type 2 known as Context Free Grammar.
  4. Type 3 Regular Grammar.



This is a hierarchy. Therefore every language of type 3 is also of type 2, 1 and 0. Similarly, every language of type 2 is also of type 1 and type 0, etc.

Type 0 Grammar:

Type 0 grammar is known as Unrestricted grammar. There is no restriction on the grammar rules of these types of languages. These languages can be efficiently modeled by Turing machines.

For example:

1.     bAa → aa  

2.     S → s  

Type 1 Grammar:

Type 1 grammar is known as Context Sensitive Grammar. The context sensitive grammar is used to represent context sensitive language. The context sensitive grammar follows the following rules:

  • The context sensitive grammar may have more than one symbol on the left hand side of their production rules.
  • The number of symbols on the left-hand side must not exceed the number of symbols on the right-hand side.
  • The rule of the form A → ε is not allowed unless A is a start symbol. It does not occur on the right-hand side of any rule.
  • The Type 1 grammar should be Type 0. In type 1, Production is in the form of V → T

Where the count of symbol in V is less than or equal to T.

For example:

1.     S → AT  

2.     T → xy  

3.     A → a  

Type 2 Grammar:

Type 2 Grammar is known as Context Free Grammar. Context free languages are the languages which can be represented by the context free grammar (CFG). Type 2 should be type 1. The production rule is of the form

1.     A → α  

Where A is any single non-terminal and is any combination of terminals and non-terminals.

For example:

1.     A → aBb  

2.     A → b  

3.     B → a  

Type 3 Grammar:

Type 3 Grammar is known as Regular Grammar. Regular languages are those languages which can be described using regular expressions. These languages can be modeled by NFA or DFA.

Type 3 is most restricted form of grammar. The Type 3 grammar should be Type 2 and Type 1. Type 3 should be in the form of

1.     V → T*V / T*  

For example:

1.     A → xy  

 

 


Pumping Lemma for L = {a | k is a prime number}

  L = {a | k is a prime number}

Let us assume L is regular.  

-> Clearly L is infinite (there are infinitely many prime numbers). From the pumping lemma, there exists a number n such that any string w of length greater than n has a “repeatable” substring generating more strings in the language L.

Let us consider the first prime number p >= n.

For example, 

if n was 50 we could use p = 53. 

From the pumping lemma the string of length p has a “repeatable” substring. We will assume that this substring is of length k >= 1.

Hence:

It should be relatively clear that p + k, p + 2k, etc., cannot all be prime but let us add k p times, then we must have:

so this would imply that (k + 1)p is prime, which it is not since it is divisible by both p and k + 1. Hence L is not regular. 




Pumping Lemma for Regular Languges


Pumping lemma used to show that language is not regular. 

What is pumping?

for regular expression

r = (a u b) (abb)* (bba u bbb), the string w= babbbbb pumps because we may decompose w into three sub strings.

w= b.  abb.  bbb

such that  b(abb)i bbb is represented by r, for every i>= 0.

in this DFA.,


the string aaabab= aa. aba.b pumps because of the cycle that the aba follows.


Suppose L is a regular Language., the there exists an integer k such that for all strings z belongs to L. , satisfying |z|>=k., we can write z= uvw where

|v| >= 1

|uv| <=k

u vw  belongs to L, for all i>=0.


Tuesday, January 18, 2022

FLAT(Formal Languages and Automata Theory) -VR23

FLAT Syllabus( VR23-CSE- Vignan Institute of Technology and Science- An Autonomous Institution ): Click Here

Unit-1 : Hand Written Notes Click Here


Unit-2 : Hand Written Notes Click Here


Unit-3 : Hand Written Notes Click Here


Unit-4 : Hand Written Notes Click Here

New notes on Push Down Automata and Turing Machine   Click Here


Unit-5 : Notes Click Here

Unit Wise Important Questions (Question Bank): Download

JNTUH FLAT Previous Questions: Download

 

Monday, January 17, 2022

Web Technologies

 Students blog for Happy Learning

Web Technologies Syllabus(R18-CSE-JNTUH): Click Here

Unit-1 : Notes Click Here

Unit-2 : Notes Click Here

Unit-3: Notes Click Here

Unit-4 : Notes Click Here

Unit-5 : Notes Click Here

Unit Wise Important Questions: Download

JNTUH Unit Wise Previous Questions: Download


ppts on Unit-5(Java Script)

Presentations on Java Script

Introduction to Java Script, First Java Script Program & Variables in Java Script ppt

Functions & Event Handlers, Form Validation in Java Script ppt

ppts on Unit-4 (JSP)

 Presentations on JSP - Java Server Pages

Introduction to JSP ppt

JSP Declarative Tags ppt

JSTL Tags & Directives ppt

Cookies & Sessions in JSP ppt


ppts on Unit-3( Servlets)

 Presentations on Servlets 

What is Servelet? ppt

Introduction to Servlet ppt

Servlet API ppt

Deploying Servlet ppt

Connecting Servlet with Tomcat ppt

Connecting Database with Servlet ppt

ppts on UNIT-2 (HTML & XML)

 Presentations on HTML & XML

HTML Forms ppt

HTML Tables ppt

HTML Frames ppt

Basic Building Blocks of XML Documents ppt

XML DOM ppt

XML DTD ppt

ppts on Unit-1(PHP)

 Presentations on PHP 

    PHP Introduction ppt

    PHP Data Types ppt

    PHP Form-Handling ppt

    PHP File Handling ppt

    PHP Functions ppt

    PHP Operators ppt

    PHP MySql ppt

    PHP SQLDB ppt


Wednesday, December 8, 2021

Servlet Packages & Servlet API

 Servlet Packages

Java Servlets are Java classes run by a web server that has an interpreter that supports the Java Servlet specification. Servlets can be created using the javax.servlet and javax.servlet.http packages, which are a standard part of the Java's enterprise edition, an expanded version of the Java class library that supports large-scale development projects.

These classes implement the Java Servlet and JSP specifications. At the time of writing this tutorial, the versions are Java Servlet 2.5 and JSP 2.1.

Java servlets have been created and compiled just like any other Java class. After you install the servlet packages and add them to your computer's Class path, you can compile servlets with the JDK's Java compiler or any other current compiler.

Servlet API:   There are two packages that are required to build servlets.

1. javax.servlet         2.javax.servlet.http.

In general javax.servlet package has all the classes/interfaces not directly tied to HTTP, and javax.servlet.http package has the classes/interfaces that deal with the http protocol.

 1. javax.servlet package:

There are number of interfaces and classes present in this package, they are described below.

Interfaces:

Servlet: Declares life cycle methods for a servlet ServletConfig: Allows servlets to get initialization parameters ServletContext: Enables servlets to log events ServletRequest: Used to read data from a 


Classs:

     GenericServlet: Implements the Servlet and ServletConfig

ServletInputStream: Provides an input stream for reading requests from a client ServletOutputStream: Provides an output stream for writing responses to a client. ServletException: Indicates that a servlet error occurred.


Following are the interfaces and their methods:

Servlet Interface:

void init(): Called when the servlet is initialized

void service(): Called to process a request from a client void destroy(): Called when the servlet is unloaded

ServletConfig getServletConfig(): Returns a ServletConfig object that contains any initialization parameters

String getServletInfo: Returns a string describing the servlet

ServletConfig Interface:

ServletContext getServletContext: Returns the context for this servlet.

String getInitParmeter(String param): Returns the value of the initialization parameter name param.

getInitParameterNames(): Returns all initialization parameter names

 ServletContext interface:

getAtrribute(String attr): Returns the value of the server attribute named attr. String 

getServiceInfo(): Returns information about the server.

Servlet getServlet(String sname): Returns the servlet named sname. getServletNames(): Returns the names of servlets in the server

 ServletRequest Interface:

String getParameter(String pname): Returns the value of the parameter named pname getParameterNames(): Returns the parameter names for this request

String[ ] getParameterValues(): Returns the parameter values for this request String getProtocol(): Returns a description of the protocol

String getServerName(): Returns the name of the serverIntgetServerPort():Returns the port number.

 

ServletResponse Interface:

PrinterWriter getWriter(): Returns a PrintWriter that can be used to write character data to the response.

ServletOutputStream getOutputStream(): Returns a ServletOutputStream that can be used to write binary data to the response.

 Following are the classes and their methods:

GenericServlet class implements Servlet and ServletConfig interface.

Methods: public void init(), public void destroy(), public abstract void service()

 

ServletInputStream class extends InputStream. It is implemented by the server and provides an input stream that a servlet developer can use to read the data from a client request. In addition to this, one more method is added which returns the actual number of bytes read Int readLine(byte[ ] buffer, int offset, int size)

 

ServletOutputStream class extends OutputStream. It defines the print() and println() methods, which output data to the stream.

 

ServletException class indicates that a servlet problem has occurred.

The class has the following contructor ServletException( ) & ServletException(String s)


 

2. javax.servlet.http package:

There are number of classes and interfaces present in this package, they are as follows:

 

Interface

HttpServletRequest: Enables servlets to read data from an HTTP request HttpServletResponse: Enables servlets to write data to an HTTP response. HttpSession: Allows session data to be read and written HttpSessionContext: Allows sessions to be managed

 

Class

HttpServlet: Provides methods to handle HTTP requests and responses Cookie: Allows state information to be stored on a client machine

Following are the interfaces and their methods description HttpServletRequest Interface

Cookie[ ] getCookies: Returns an array of the cookies in this request

String getMethod(): Returns the HTTP method for this request String getQueryString(): Returns any query string in the URL

String getRemoteUser(): Returns the name of the user who issued this request. String getRequestedSessionId(): Returns the ID of the session

String getServletPath(): Returns the part of the URL that identifies the servlet

 

HttpServletResponse Interface

Void addCookie(Cookie cookie): Adds cookie to the HTTP response. Void sendError(int c): Send the error code c to the client

Void sendError(int c , String s): Send the error code c and the message s Void sendRedirect(String url): Redirects the client to url

A simple Java program to find the inverse of a given matrix

  import java.util.Scanner; public class MatrixInverse { public static void main (String[] args) { Scanner scanner =...