The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register
|
I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Ullman (Compiler Design) Edition 2 Exercise 3.3 Question 3 (Page No. 125)
+1
vote
12
views
In a string of length $n$, how many of the following are there?
Prefixes.
Suffixes.
Proper prefixes.
Substrings.
Subsequences.
ullman
compiler-design
strings
descriptive
asked
Aug 5
in
Compiler Design
by
Lakshman Patel RJIT
Veteran
(
55k
points)
edited
Aug 5
by
Lakshman Patel RJIT
|
12
views
answer
comment
Please
log in
or
register
to add a comment.
Please
log in
or
register
to answer this question.
1
Answer
0
votes
$n + 1 (n$ prefixes for $n$ characters, plus the empty string$)$
$n + 1 ($similar to $(a))$
$n - 1 (n$ prefixes for $n$ characters, minus the string itself$)$
$n [1$ character substring$] + (n - 1) [2$ character substring$] + \dots + 1 = \dfrac{n (n + 1)}{2}.$ Add $1$ to include the empty substring.
$\displaystyle{}\sum_{i=0}^{n} {^{n}C_{i}} = 2^{n}$, if you include the empty subsequence.
answered
Nov 8
by
pritishc
Active
(
1k
points)
edited
Nov 8
by
Lakshman Patel RJIT
comment
Please
log in
or
register
to add a comment.
← Prev. Qn. in Sub.
Next Qn. in Sub. →
← Prev.
Next →
Related questions
0
votes
0
answers
1
Ullman (Compiler Design) Edition 2 Exercise 3.3 Question 5 (Page No. 125 - 126)
Write regular definitions for the following languages: All strings of lowercase letters that contain the five vowels in order. All strings of lowercase letters in which the letters are in ascending lexicographic order. Comments, ... substring abb. All strings of a's and b's that do not contain the subsequence abb.
asked
Aug 5
in
Compiler Design
by
Lakshman Patel RJIT
Veteran
(
55k
points)
|
13
views
ullman
compiler-design
strings
descriptive
0
votes
0
answers
2
Ullman (Compiler Design) Edition 2 Exercise 3.3 Question 4 (Page No. 125)
Most languages are case sensitive, so keywords can be written only one way, and the regular expressions describing their lexeme is very simple. However, some languages, like SQL, are case insensitive, so a keyword ... in a case-insensitive language. Illustrate the idea by writing the expression for "select" in SQL.
asked
Aug 5
in
Compiler Design
by
Lakshman Patel RJIT
Veteran
(
55k
points)
|
2
views
ullman
compiler-design
regular-expressions
lexeme
descriptive
0
votes
1
answer
3
Ullman (Compiler Design) Edition 2 Exercise 3.3 Question 2 (Page No. 125)
Describe the languages denoted by the following regular expressions: $a(a\mid b)^{\ast}a.$ $((\epsilon\mid a)b^{\ast})^{\ast}.$ $(a\mid b)^{\ast}a(a\mid b)(a\mid b).$ $a^{\ast}ba^{\ast}ba^{\ast}ba^{\ast}.$ $(aa\mid bb)^{\ast}((ab\mid ba)(aa\mid bb)^{\ast}(ab\mid ba)(aa\mid bb)^{\ast})^{\ast}.$
asked
Aug 5
in
Compiler Design
by
Lakshman Patel RJIT
Veteran
(
55k
points)
|
30
views
ullman
compiler-design
regular-expressions
descriptive
0
votes
0
answers
4
Ullman (Compiler Design) Edition 2 Exercise 3.3 Question 1 (Page No. 125)
Consult the language reference manuals to determine the sets of characters that form the input alphabet (excluding those that may only appear in character strings or comments), the lexical form of numerical constants, and the lexical form of identifiers, for each of the following languages: C C++ C# Fortran Java Lisp SQL
asked
Aug 5
in
Compiler Design
by
Lakshman Patel RJIT
Veteran
(
55k
points)
|
29
views
ullman
compiler-design
lexical-analysis
specification-of-tokens
descriptive
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
Recent Posts
ECIL Interview Experience
Linear Algebra Important Points
GATE 2020
OFFICIAL GATE MOCK TEST RELEASED
IIITH: Winter Research Admissions 2019 (For Spring 2020)
All categories
General Aptitude
1.9k
Engineering Mathematics
7.5k
Digital Logic
2.9k
Programming and DS
4.9k
Algorithms
4.3k
Theory of Computation
6.2k
Compiler Design
2.1k
Operating System
4.5k
Databases
4.1k
CO and Architecture
3.4k
Computer Networks
4.1k
Non GATE
1.5k
Others
1.5k
Admissions
595
Exam Queries
576
Tier 1 Placement Questions
23
Job Queries
72
Projects
17
Follow @csegate
Recent Blog Comments
Not really. It was excluding shipping I guess....
Ok sir. Actually pricing on Flipkart is 200 less...
NO.
Is this application open for 2020 graduates i.e....
@Ayush Upadhyaya sir any approximate idea...
50,645
questions
56,609
answers
195,893
comments
102,319
users