Awesome q2a theme
0 votes

Given is a Regular Expression,


If we want ot generate strings from this regular language , then while generating a string do we need to keep value of * same for a string or can we change it for every digit in the regular expression.

For eg-

Given RE is 0*(10*)*

when we are generating a string say 0^2(1 0^2)^2 , So my question is that whether these values of * should be same in every string or can they be changed like 0^4(1 0^3)^6 in a string . Please answer this since, I am finding it difficult to solve these type of questions.


in Theory of Computation by (10 points) | 16 views

1 Answer

+1 vote
Best answer
k* means any number of zero including NULL ( zero k's)

and you can have any combination you want.

you can just keep expanding 0*, keeping everything else unitary

ex: 0(10) , 00(10),000(10), 0000(10) ..

or, 00(100), 00(100)..

or, 0(111111111),

or simply 0, 00, 000, 0000, 00000

they all are stings from this R.E

hope you get what you have asked.

(No, you don't need to keep the value of * same)
by (87 points)
selected by
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.
Top Users Jul 2020
  1. Shaik Masthan

    39 Points

  2. hiteshpujari

    9 Points

  3. Venkatesh Akhouri

    6 Points

  4. Meghana518

    6 Points

  5. bittujash

    6 Points

  6. Pawan_k

    6 Points

  7. rits78671

    6 Points

  8. Sumaiyas

    6 Points

  9. srestha

    6 Points

  10. RavGopal

    4 Points

7,545 questions
1,783 answers
90,483 users