0 votes
0 votes
As for a Finite Automata, we say a finite automata accepts a language if it accepts all strings present in the language as well as REJECTS all strings which are not present in the language.

Is the definition for a regular language the same as that of a finite automata ie, a regular expression should represent all strings of the regular language as well as NOT represent any strings not part of the language ??

Pls clear this.
in Theory of Computation
5 points

1 Answer

0 votes
0 votes

Alternatively, a regular language can be defined as a language recognized by a finite automaton. The equivalence of regular expressions and finite automata is known as Kleene's theorem (after American mathematician Stephen Cole Kleene). In the Chomsky hierarchy, regular languages are the languages generated by Type-3 grammars....

A regular language is a language that can be expressed with a regular expression or a deterministic or non-deterministic finite automata or state machine...

A language is a set of strings which are made up of characters from a specified alphabet, or set of symbols. Regular languages are a subset of the set of all strings.

Regular languages are used in parsing and designing programming languages and are one of the first concepts taught in computability courses.

These are useful for helping computer scientists to recognize patterns in data and group certain computational problems together — once they do that, they can take similar approaches to solve the problems grouped together. Regular languages are a key topic in computability theory...


1. https://www.cse.iitb.ac.in/~trivedi/courses/cs208-spring14/lec04.pdf 


2. https://gateoverflow.in/1291/Gate-cse-2006-question-34 


3. https://gateoverflow.in/1914/Gate-cse-2014-set-1-question-36



5 points

1 comment

@@ The definition says that a regular language is one where some finite automata exists recognizing it ..

$$ A regular language satisfies the following equivalent properties: :

# It is the language of a regular expression (by the above definition)..

## It is the language accepted by a nondeterministic finite automaton (NFA) ..

### It is the language accepted by a deterministic finite automaton (DFA)..


1. https://en.wikipedia.org/wiki/Regular_language#Equivalent_formalisms 


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
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.